dsfds' blog

学海无涯，回头是岸

0%

LeetCode | 61 旋转链表

发表于 更新于 分类于 Valine：

题目

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

示例

  • 输入：1->2->3->4->5，k=2
  • 输出：4->5->1->2->3

题解

题目名字叫旋转链表，其实就是循环移动。最简单的思路是：遍历链表找到尾节点的前一节点，然后把尾节点从头插入链表，对这个过程执行 k 次即可。这样做算法的时间复杂度为 O(kn)。考虑到是循环移动，我们可以对算法进行改进。

首先考虑 k 小于链表长度的情况，链表循环向右移动 k 次，不就相当于把链表练成环，然后尾节点位置向左移动 k 次吗？下面这个图展示了这个过程。

对于 k 大于链表长度的情况，先构成环，沿着环一直移动就行。这种方法的问题在于我们需要逆向移动单链表的指针，即每次需要找到单链表前驱的前驱，这是很难做到的，但我们可以先行将单链表进行逆序，然后移动指针，确定最终的头尾节点后再把链表逆序回来即可。

更进一步的，在环中逆序移动指针 k 次，就相当于顺序移动指针 n-k 次，其中 n 是链表的长度。基于这种想法，我们再加以改进，得到下面的解法。

先把指针 p 从头向后移动到尾，直到循环移动的次数 k==0。在此过程中，如果 p 指向了空节点，说明到了链表尾部，k 大于链表的长度，这时候我们可以利用循环的特点，对链表的长度减一值进行取模运算，得到的值是我们需要再移动到位置。然后按照上述的方法进行指针移动即可。最终代码如下所示。

LeetCodeSolution61.cview raw
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
ListNode *rotateRight(ListNode *head, int k)
{
    if (head == NULL || k <= 0)
        return head;
    ListNode *pre, *last, *p;
    ListNode tmpNode;
    tmpNode.next = head;
    last = &tmpNode;
    p = head;
    int ak = k;
    while (k > 0){
        // 滑动指针来代替循环
        if (p == NULL) {
            int tmp = ak - k;
            pre = &tmpNode;
            p = head;
            k = ak % tmp;
            if (k == 0) break;
        }
        pre = p;
        p = p->next;
        k--;
    }
    while (p != NULL) {
        last = last->next;
        pre = p;
        p = p->next;
    }
    if (last != &tmpNode) {
        pre->next = head;
        tmpNode.next = last->next;
        last->next = NULL;
    }
    return tmpNode.next;
}