反转链表
大海我来了
共 1364字,需浏览 3分钟
· 2021-02-02
难度:简单
来源:206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
思路:
定义输出链表 prev; 在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用;
顺序遍历链表 head , 将其中的元素移入链表 prev ; 图解如下; 而递归的思路其实就是传递 2 个参数,prev 和 curr ,分别用来指定反转后和前的链表,思路是差不多的。
题解一:迭代
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
// 方法一:迭代实现
let prev = null
let curr = head
while (curr != null) {
let next = curr.next
curr.next = prev
prev = curr
curr = next
}
return prev
};
题解二:递归
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
const reverse = (prev, curr) => {
if (!curr) {
return prev
}
let next = curr.next
curr.next = prev
return reverse(curr, next)
}
return reverse(null, head)
};
评论
C#控制反转常见面试题
简介 控制反转(IoC)是软件工程中的一个设计模式,它将对象的创建和控制权从客户端转移到容器。在传统的编程方式中,客户端需要创建和管理对象,这会导致对象之间存在强耦合关系。使用IoC后,容器负责创建和管理对...
llovebo
0
反转来了!iOS17将支持这些设备!
昨天我看到新闻称iOS17将不支持A11一下的设备也就是说包括iPhoneX以及iPhone8/Plus设备,反转来了,这位网友表示是支持的 上面这位网友表示,去年支持 iOS 16 的设备今年也将被列入 iOS 17 的支持名单,包括所有搭载...
宅哥技术
0