返回 LeetCode 刷题

Markdown File

反转链表

反转链表.md

下载原文件打开 Vercel 原文件
1我们做一下反转链表的习题206：
2
3给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
4输入：head = [1,2,3,4,5]
5输出：[5,4,3,2,1]
6
7输入：head = [1,2]
8输出：[2,1]
9示例 3：
10
11输入：head = []
12输出：[]
13看一下灵神的代码：方法一：递归（尾插法）
14递归递归，有递有归。
15
16我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。
17
18新链表的末尾节点在哪？就是当前节点的 next。具体实现如下。
19
20class Solution:
21 # 首先「递」到链表末尾，把末尾节点作为新链表的头节点 rev_head
22 # 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
23 def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
24 # 判断 head is None 是为了兼容一开始链表就是空的情况
25 if head is None or head.next is None:
26 return head # 链表末尾，即下面的 rev_head
27 rev_head = self.reverseList(head.next) # 「递」到链表末尾，拿到新链表的头节点
28 tail = head.next # 在「归」的过程中，head.next 就是新链表的末尾
29 tail.next = head # 把 head 插在新链表的末尾
30 head.next = None # 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
31 return rev_head
32答疑
33问：为什么不写 head.next = null 的代码，会提示「超出内存限制」？这应该是超时呀？
34
35答：这和力扣的判题机制有关，评测机会先把链表转成字符串，再去比对答案。这会遍历链表，如果链表有环，生成的字符串会无限延长，在超时之前就超出内存限制了。
36
37复杂度分析
38时间复杂度：O(n)，其中 n 为链表节点个数。
39空间复杂度：O(n)。递归需要 O(n) 的栈空间。
40方法二：迭代（头插法）
41视频讲解：【基础算法精讲 06】，制作不易，欢迎点赞~
42
43简单理解：比如链表为 1→2→3。创建一个新的空链表，然后用头插法依次把节点 1,2,3 插到这个新链表的头部，就得到了链表 3→2→1，这正是反转后的链表。
44
45头插法的意思是，把一个节点 node 指向链表头节点（node.next 更新为链表头节点），那么 node 就插在了链表的左侧，新链表的头节点为 node。
46
47对于链表 1→2→3，结合代码来说，顺序为：
48
49第一轮循环结束后，得到链表 1。
50第二轮循环结束后，得到链表 2→1。
51第三轮循环结束后，得到链表 3→2→1。
52注：代码每轮循环结束后，pre 表示最新得到的链表。
53
54class Solution:
55 def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
56 pre = None
57 cur = head
58 while cur:
59 nxt = cur.next
60 cur.next = pre # 把 cur 插在 pre 链表的前面（头插法）
61 pre = cur
62 cur = nxt
63 return pre
64复杂度分析
65时间复杂度：O(n)，其中 n 为链表节点个数。
66空间复杂度：O(1)。
67
68c语言实现：一些错误
691. node没有初始化
702. 没保存val
713. 只执行一次
724. 没有循环处理整个链表
735. pre->next = node->next逻辑错误
74//这里是创建了新节点
75struct ListNode* reverseList(struct ListNode* head)
76{
77 struct ListNode* header =
78 malloc(sizeof(struct ListNode));
79
80 header->next = NULL;
81
82 while(head != NULL)
83 {
84 struct ListNode* node =
85 malloc(sizeof(struct ListNode));
86
87 node->val = head->val;
88
89 node->next = header->next;
90
91 header->next = node;
92
93 head = head->next;
94 }
95 struct ListNode* ans = header->next;
96//指向空节点的下一个
97 free(header);
98
99 return ans;
100}
101
102使用栈的思路：
103struct ListNode* reverseList(struct ListNode* head)
104{
105 struct ListNode* newHead = NULL;
106//newhead作为定位指针，当后续节点相连的时候指向当前的最前面的节点
107 while(head != NULL)
108 {
109 struct ListNode* node =
110 malloc(sizeof(struct ListNode));
111
112 node->val = head->val;
113
114 node->next = newHead;
115
116 newHead = node;
117
118 head = head->next;
119 }
120
121 return newHead;
122}
123递归的思路：
124struct ListNode* reverseList(struct ListNode* head)
125{
126 if(head == NULL || head->next == NULL)
127 {
128 return head;
129 }
130 struct ListNode* newHead =
131 reverseList(head->next);
132
133 head->next->next = head;
134
135 head->next = NULL;
136
137 return newHead;
138}
139reverseList(head)=把head后面的链表先反转
140然后把head接到最后面
141
142例如：reverseList(1)=reverseList(2)+把1接到最后
143
144而：
145reverseList(2)=reverseList(3)+把2接到最后
146
147最终：
148
1493
150
151↓
152
1533 -> 2
154
155↓
156
1573 -> 2 -> 1
Rendered Preview

我们做一下反转链表的习题206：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = [1,2]
输出：[2,1]
示例 3：

输入：head = []
输出：[]
看一下灵神的代码：方法一：递归（尾插法）
递归递归，有递有归。

我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。

新链表的末尾节点在哪？就是当前节点的 next。具体实现如下。

class Solution:
# 首先「递」到链表末尾，把末尾节点作为新链表的头节点 rev_head
# 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 判断 head is None 是为了兼容一开始链表就是空的情况
if head is None or head.next is None:
return head # 链表末尾，即下面的 rev_head
rev_head = self.reverseList(head.next) # 「递」到链表末尾，拿到新链表的头节点
tail = head.next # 在「归」的过程中，head.next 就是新链表的末尾
tail.next = head # 把 head 插在新链表的末尾
head.next = None # 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
return rev_head
答疑
问：为什么不写 head.next = null 的代码，会提示「超出内存限制」？这应该是超时呀？

答：这和力扣的判题机制有关，评测机会先把链表转成字符串，再去比对答案。这会遍历链表，如果链表有环，生成的字符串会无限延长，在超时之前就超出内存限制了。

复杂度分析
时间复杂度：O(n)，其中 n 为链表节点个数。
空间复杂度：O(n)。递归需要 O(n) 的栈空间。
方法二：迭代（头插法）
视频讲解：【基础算法精讲 06】，制作不易，欢迎点赞~

简单理解：比如链表为 1→2→3。创建一个新的空链表，然后用头插法依次把节点 1,2,3 插到这个新链表的头部，就得到了链表 3→2→1，这正是反转后的链表。

头插法的意思是，把一个节点 node 指向链表头节点（node.next 更新为链表头节点），那么 node 就插在了链表的左侧，新链表的头节点为 node。

对于链表 1→2→3，结合代码来说，顺序为：

第一轮循环结束后，得到链表 1。
第二轮循环结束后，得到链表 2→1。
第三轮循环结束后，得到链表 3→2→1。
注：代码每轮循环结束后，pre 表示最新得到的链表。

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre # 把 cur 插在 pre 链表的前面（头插法）
pre = cur
cur = nxt
return pre
复杂度分析
时间复杂度：O(n)，其中 n 为链表节点个数。
空间复杂度：O(1)。

c语言实现：一些错误

  1. node没有初始化

  2. 没保存val

  3. 只执行一次

  4. 没有循环处理整个链表

  5. pre->next = node->next逻辑错误
    //这里是创建了新节点
    struct ListNode* reverseList(struct ListNode* head)
    {
    struct ListNode* header =
    malloc(sizeof(struct ListNode));

    header->next = NULL;

    while(head != NULL)
    {
    struct ListNode* node =
    malloc(sizeof(struct ListNode));

     node->val = head->val;

 node->next = header->next;

 header->next = node;

 head = head->next;

    }
    struct ListNode* ans = header->next;
    //指向空节点的下一个
    free(header);

    return ans;
    }

使用栈的思路：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* newHead = NULL;
//newhead作为定位指针，当后续节点相连的时候指向当前的最前面的节点
while(head != NULL)
{
struct ListNode* node =
malloc(sizeof(struct ListNode));

    node->val = head->val;

    node->next = newHead;

    newHead = node;

    head = head->next;
}

return newHead;

}
递归的思路：
struct ListNode* reverseList(struct ListNode* head)
{
if(head == NULL || head->next == NULL)
{
return head;
}
struct ListNode* newHead =
reverseList(head->next);

head->next->next = head;

head->next = NULL;

return newHead;

}
reverseList(head)=把head后面的链表先反转
然后把head接到最后面

例如：reverseList(1)=reverseList(2)+把1接到最后

而：
reverseList(2)=reverseList(3)+把2接到最后

最终：

3

↓

3 -> 2

↓

3 -> 2 -> 1