leetcode题记-206.反转链表

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?

来源:力扣(LeetCode)

题解

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
register ListNode *prev = NULL;
register ListNode* curr = head;
register ListNode* temp;
while (curr != NULL) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
return prev;
}
};

结果

执行用时 : 16 ms, 在所有 C++ 提交中击败了53.05%的用户
内存消耗 : 9.2 MB, 在所有 C++ 提交中击败了28.08%的用户

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* p = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return p;
}
};

结果

执行用时 : 12 ms, 在所有 C++ 提交中击败了85.51%的用户
内存消耗 : 9.1 MB, 在所有 C++ 提交中击败了47.27%的用户

这个递归法有点意思,看了很久才赚过弯来。
在读代码+一步步画图解析之后,终于明白了其中的原理。
一行一行的讲解吧:

1
if (head == NULL || head->next == NULL) return head;

第一行是每个递归都需要的开始返回的条件。
第一个条件head == NULL 是处理[]这样的链表的特殊条件,并且在第二个条件head->next == NULL之前进行运算是为了防止在[]这样的空链表中运行head->next导致内存访问错误。
第二个条件是正常的递归跳出。搭配第2句、第5句就可以将尾节点不断的往上层调用栈返回。

1
ListNode* p = reverseList(head->next);

使用一个临时指针将第一句返回的尾节点存起来,以便最后返回。

1
2
head->next->next = head;
head->next = NULL;

这两句要一起看,我们先来看看每一次递归调用栈运行的时候链表的情况吧,以链表[1,2,3,4,null]为例。n在那个节点下面就代表那个节点的next指向null,h代表head指向,p代表临时指针p指向(最后返回的p也是这个)。

初始状态:

1
2
1->2->3->4
n

第3层调用栈

1
2
3
      h  p
1->2->3<-4
n

第2层调用栈

1
2
3
   h     p
1->2<-3<-4
n

第1层调用栈

1
2
3
h        p
1<-2<-3<-4
n

可以看出在head指向的那个节点处运算过后就会将后一个节点的next指向本节点,以此往复就会将整条链表都换向。
而将本节点的next指向null我觉得是加强算法完整性来做的,因为是一个函数自己递归,所以要保证最后返回的链表最后一个节点要指向null,所以需要这一步。
可以看出p指针永远都是指向尾节点,并且一层一层的往上返回,感觉这一点设计很巧妙就是了。

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/09/07/leetcode-206-reverseList/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,