LeetCode第206题反转链表（Python）_leetcode 206

题目描述

反转一个单链表。

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题方法和思路

定义游标用于反转($O(n)$)

定义三个游标，p,q,r。

1->2->3->4->5->NULL
^  ^  ^
p  q  r
1
2
3

进行一下几个步骤：

1. 初始话的时候令p.next = None
2. 当r is not None时，反转p,q,即令q.next = p
3. 三个游标整体前进一步。并且不断循环步骤2。
4. 当r is None，表示p,q,r已经走到链表的末尾，进行最后一个p,q的反转返回q即可

在三个游标中r游标起引路作用，不至于在反转过程中找不到余下的链表。

复杂度：

1. 时间复杂度：只需遍历一次链表，因此时间复杂度为$O(n)$
2. 空间复杂度：只需使用三个变量而不用考虑链表的长度，因此空间复杂度为$O(1)$

核心代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        p = None
        q = head
        r = head.next
        while r is not None:
            # reverse
            q.next = p
            # 前进
            p,q,r = q,r,r.next    
        # r is None,走到最后
        q.next = p
        return q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

迭代

思路：
将链表：
$$n_1\to n_2\to ...\to n_k\to n_{k+1}\to n_{k+2}\to ...\to n_m$$
以$n_k$之后为界限将链表看成两部分，令head = n_k，则之后的部分调用递归调用reverseList(head.next)可以完成反转，反转之后如下：
$$n_1\to n_2\to ...\to n_k\to n_{k+1}\leftarrow n_{k+2}\leftarrow ...\leftarrow n_m$$
并返回一个$n_k$之后节点反转之后的新的头结点即$n_m$。
则当前要考虑的就是怎么把$n_k$纳入进来，很简单，只需将head.next节点的下一个节点指向head节点即可反转$n_k$，$n_{k+1}$之间的指向关系。即head.next.next = head。
由于当前head连接上head之后的反转链表，并且反转之后，head节点在新链表的最后一个节点，因此要添加head.netx = None标志当前链表的结束。
**复杂度：**时间和空间复杂度都为$O(n)$。
核心代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        # 反转当前节点之后的链表
        new_head = self.reverseList(head.next)
        # 拼接当前节点和之后的已经反转好的链表,
        head.next.next = head
        # 翻转以后当前head节点为最后的有效节点，应该添加最后的None标志链表结束
        head.next = None
        return new_head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17