反转链表
大海我来了
共 1364字，需浏览 3分钟
·
2021-02-02 00:51
难度：简单
来源：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)
};
评论