想要精通算法和SQL的成长之路 - 旋转链表

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 旋转链表

原题链接

由于k的大小可能超过链表长度，因此我们需要根据链表长度取模。那么我们首先需要去计算链表的长度是多少：

if (head == null) {
    return head;
}
// 计算链表的长度
ListNode tmp = head;
int len = 0;
while (tmp != null) {
    len++;
    tmp = tmp.next;
}
// 取模
k = k % len;
1
2
3
4
5
6
7
8
9
10
11
12

然后，我们用双指针去完成剩余的步骤：

1. 准备快慢两个指针，分别指向头结点。

2. fast指针向后移动k位。那次是fast指针后的链表部分。就是需要迁移到链表头部的区域。
   

3. 快慢指针同时向后移动，直到fast指针指向链表的结尾处
   

4. 此时，fast.next应该指向head（此时链表成环），新的头结点应该更细为slow.next，更新完毕后，slow.next断开（解除环）
   
   代码如下：

ListNode slow = head, fast = head;
// 快指针先移动k位
for (int i = 0; i < k; i++) {
    fast = fast.next;
}
// 快慢指针同时移动，直到fast到达链表末尾
while (fast.next != null) {
    fast = fast.next;
    slow = slow.next;
}
// 末尾指向原Head，形成环
fast.next = head;
// 认定新的头结点
head = slow.next;
// 解除环状
slow.next = null;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

最终完整代码如下：

public ListNode rotateRight(ListNode head, int k) {
    if (head == null) {
        return head;
    }
    // 计算链表的长度
    ListNode tmp = head;
    int len = 0;
    while (tmp != null) {
        len++;
        tmp = tmp.next;
    }
    k = k % len;
    ListNode slow = head, fast = head;
    // 快指针先移动k位
    for (int i = 0; i < k; i++) {
        fast = fast.next;
    }
    // 快慢指针同时移动，直到fast到达链表末尾
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    // 末尾指向原Head，形成环
    fast.next = head;
    // 认定新的头结点
    head = slow.next;
    // 解除环状
    slow.next = null;
    // 返回新头结点
    return head;
}
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