206反转链表

206. 反转链表

题目

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

示例一:

1
2
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

示例二:

1
2
输入:head = [1,2]
输出:[2,1]

示例 三:

1
2
输入:head = []
输出:[]

题解

方法一:迭代

在遍历链表时,将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

1
2
3
4
5
6
7
8
9
10
const reverseList = function(head) {
let cur = head,prev = null,tmp;
while(cur){
tmp = cur.next;
cur.next = prev;
prev = cur;
cur = tmp;
}
return prev;
};

复杂度分析

  • 时间复杂度:O(n),其中 n 是链表的长度。需要遍历链表一次。
  • 空间复杂度:O(1)。

方法二 递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
//递归终止条件是当前为空,或者下一个节点为空
if(head === null || head.next === null){
return head;
}
//这里的cur就是最后一个节点
const cur = reverseList(head.next);
//如果链表是 1->2->3->4->5,那么此时的cur就是5
//而head是4,head的下一个是5,下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环,需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur,也就是最后一个节点
return cur;
};

本题题解建议参考 点这里

参考链接