LeetCode 61. 旋转链表（中）

典型的双指针问题，由于是链表循环问题，首尾相接之后，基于单指针也可以完成。

题目

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例

示例 1:

1
2
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

1
2
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

考察知识点

快慢指针、链表

核心思想

方法一、快慢指针

用快慢指针来解，快指针先走k步，然后两个指针一起走，当快指针走到末尾时，慢指针的位置就是新顺序的尾结点，慢指针的下一个位置是新的顺序的头结点，这样就可以旋转链表了，自信满满的写完程序，放到OJ上跑，以为能一次通过，结果跪在了各种特殊情况，首先一个就是当原链表为空时，直接返回NULL，还有就是当k大于链表长度和k远远大于链表长度时该如何处理，我们需要首先遍历一遍原链表得到链表长度n，然后k对n取余，这样k肯定小于n。 

1
2
3
4
5
6
7
8
9
1->2->3->4->5->NULL, k=2
^     ^
s     f
1->2->3->4->5->NULL
      ^     ^
      s     f
4->5->1->2->3->NULL
      ^     ^
      s     f
方法二、单指针
这道题还有一种解法，跟上面的方法类似，但是不用快慢指针，一个指针就够了，原理是先遍历整个链表获得链表长度n，然后此时把链表头和尾链接起来，在往后走 n - k % n 个节点就到达新链表的头结点前一个点，这时断开链表即可，从new start开始截取n个node为新的链表。

1
2
3
4
5
6
7
1->2->3->4->5->NULL, k=2
头尾相接走n-k%n个(3个)节点
1->2->3->4->5->1->2->3->4->5->NULL
      ^
      new start
这时断开3和4之间的连接 就得到了新的链表
4->5->1->2->3->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
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 rotateRight(self, head: ListNode, k: int) -> ListNode:
        length = listLength(head)
        if length == 0:
            return None
        k = k % length
        if k == 0 or length == 1:  # k=0意味着不需要调整
            return head
        # 哑结点
        dummy = ListNode(None)
        dummy.next = head
        slow_pointer = head
        fast_pointer = head
        i = 0
        while i < k:
            fast_pointer = fast_pointer.next
            i += 1
        while fast_pointer.next != None:
            fast_pointer = fast_pointer.next
            slow_pointer = slow_pointer.next
        
        dummy.next = slow_pointer.next
        slow_pointer.next = None
        fast_pointer.next = head

        return dummy.next

print("leet code accept!!!")
Input = [[1,2], [1], [1, 2, 3, 4, 5], [0, 1, 2]]
Input1 = [2, 1, 2, 4]
Answer = [[1,2], [1], [4, 5, 1, 2, 3], [2, 0, 1]]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.rotateRight(createList(Input[i]), Input1[i])
        printList(reslut)
        print(Answer[i])
        # print(reslut == Answer[i])

时间复杂度：\(O(n)\)，遍历一遍链表，获取长度，再遍历一遍基于双指针找到新的顺序的头结点
执行用时：40 ms, 在所有 Python3 提交中击败了65.50%的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了5.43%的用户

  • 方法二的实现
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
class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        p = head
        if p == None:  # 长度为0的链表
            return None
        else:
            length = 1
        while p.next != None:
            length += 1
            p = p.next
        
        if length == 0:
            return None
        
        dummy = ListNode(None)
        p.next = head  # 首尾相接

        i = 0
        k = length - k % length
        while i < k:  # 从尾部出发 往后走length - k % length步 达到新链表的头结点前一个点**
            p = p.next
            i += 1

        i = 0
        dummy.next = p.next
        p.next = None  # 这里断开之 之前的循环也就跟着断开了 就得到了新的链表

        return dummy.next

时间复杂度：\(O(n)\)，遍历一遍链表，获取长度，再遍历一遍找到断开位置。
执行用时 :56 ms, 在所有 Python3 提交中击败了17.40%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.43%的用户

参考链接

LeetCode Rotate List 旋转链表