Description

Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

从倒数第k个结点位置旋转链表：首尾相连，以倒数第k个结点为新head。

Solution

这种寻找链表倒数第k的方法，通常使用快慢指针。

快指针先前进k个结点，然后两个指针同时前进，当到快指针达链表尾部时， 两个指针相差k个结点，此时慢指针指向倒数第k个结点。

 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

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || k == 0 {
        return head
    }

    fast := &ListNode{
        Next: head,
    }
    slow := fast

    // fast 先前进
    steps := 0
    for steps < k {
        fast = fast.Next
        steps++
        if fast.Next == nil {
            k = k % steps
            if k == 0 {
                return head
            }
            steps = 0
            fast = slow
        }
    }

    // 再同时前进
    for fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }

    fast.Next = head
    head = slow.Next
    slow.Next = nil

    return head
}