LeetCode 92. 反转链表 II（中）

设置了反转区间的链表反转问题，先设置哑结点，然后直接从第一个遍历到最后一个，在需要反转的区间内两两交换即可。

题目

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。

示例

示例:

1
2
3
4
# 输入: 
1->2->3->4->5->NULL, m = 2, n = 4
# 输出: 
1->4->3->2->5->NULL

考察知识点

链表

核心思想

方法一、从前往后遍历两两节点交换
直觉：设置哑结点，直接从第一个遍历到最后一个，在需要翻转的区间内两两交换即可。

方法二、指针加栈
直觉：这道题没有空间复杂度要求，可以利用栈先进先出的特点结合指针解决。

Python版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
from typing import List

class ListNode():
    def __init__(self, val):
        self.val = val
        self.next = None

    def __str__(self):
        return str(self.val)


def createList(value_list: list) -> ListNode:
    """
    Create Linked List based on list
    :param value_list: list
    :return: NodeList
    """
    _len = len(value_list)
    if _len == 0:
        return None
    if _len == 1:
        return ListNode(value_list[0])
    else:
        root = ListNode(value_list[0])
        tmp = root
        for i in range(1, _len):
            tmp.next = ListNode(value_list[i])  # 声明当前节点，再把当前节点与前面节点联系在一起。
            tmp = tmp.next  # 更新tmp为下一个节点
    return root # 返回根节点


def printList(head: ListNode):
    """
    Print single node one by one in linked list
    :param head: ListNode
    :return: None
    """
    p = head
    while p != None:
        # print()
        print(p)  # 由于有ListNode实现了__str__函数 就不用调用p.val来获取节点值了
        p = p.next


def listLength(head: ListNode) -> int:
    """
    Get the length of linked list
    :param head: ListNode
    :return: int
    """
    count = 0
    p = head
    while p != None:
        count += 1
        p = p.next
    return count


class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        # 特判
        if m == n:  return head  # 不翻转
        if head == None:  return head  # 0个节点
        if head.next == None: return head  # 1个节点
        dummy = ListNode(None)  # 哑结点
        dummy.next = head  # 哑结点指向head
        pre_p = dummy  # 前指针
        p = head  # 当前指针
        count = 1  # 当前遍历的位置
        while count <= n + 1:
            if count < m: # 还未达到开始位置
                p = p.next
                pre_p = pre_p.next
            elif count == m:  # 到达开始位置，固定pre_start。
                pre_start = pre_p  # start指针的前指针
                start = p  # start指针
                p = p.next
                pre_p = pre_p.next
            elif m < count <= n:  # 超过开始翻转
                next_p = p.next  # 保留下一个位置
                cur_p = p  # 保留当前位置
                p.next = pre_p  # 当前节点断开与后续节点的链接，反向链接前一个节点。  
                p = next_p  # p指针依靠next_p向后移动
                pre_p = cur_p  # pre_p依靠cur_p指针向后移动
            else:  # 超过结束位置 count > n
                pre_start.next = pre_p  # pre_start所指节点指向扫描末尾的节点，pre_start所指节点成为了翻转之后的头节点。
                start.next = p # start所指节点指向未翻转部分的节点，start所指节点成为了翻转之后的尾节点。
            count += 1  # count 增加
        return dummy.next  # 返回哑结点的next，也就是翻转链表的新head。



Input = [[3,5], [1, 3, 5], [3, 5], [], [1], [1, 2, 3, 4, 5]]
Input1 = [1, 1, 1, 1, 1, 2]  # m表示开始位置
Input2 = [1, 3, 2, 1, 1, 4]  # n表示结束位置
Answer = [[3,5], [5, 3, 1], [5, 3], [], [1], [1, 4, 3, 2, 5]]
if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)): 
        print("-"*50)
        result = solution.reverseBetween(createList(Input[i]), Input1[i], Input2[i])
        printList(result)
        print(Answer[i])

时间复杂度：\(O(n)\)，一次遍历。
空间复杂度：\(O(1)\)，只使用了常数级别的额外空间。
执行用时 :36 ms, 在所有 Python3 提交中击败了64.03%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.00%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def reverseBetween(self, head, m, n):
        """
        :type head: ListNode
        :type m: int
        :type n: int
        :rtype: ListNode
        """

        if not head:  return None
        if not head.next: return head

        count = n - m
        dummy = ListNode(None)
        dummy.next = head
        cur = dummy
        stack = list()
        
        while m != 1:
            cur = cur.next
            m -= 1
        pre_p = cur

        while count > -1:
            cur = cur.next
            stack.append(cur)
            count -= 1
        
        tail = cur.next
        while True:
            pre_p.next = stack.pop()
            pre_p = pre_p.next
            if stack == []:
                break
        pre_p.next = tail

        return dummy.next

有效语法糖

1、 Python链表中的指针复制传递问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 假设A指针指向了节点 heda
A = head
head -> next -> None
 ^
 A
# 同时，B指针也指向A指针所指向的节点。
B = A
head -> next -> None
  ^
A & B
# 这时，移动A指针，不会影响B指针的指向。
A = A.next
head -> next -> None
  ^       ^
  B       A