旋转链表

---

6xglMn.png

https://leetcode-cn.com/problems/rotate-list/

准备工作：

• 本题用到了一个思想，找到链表倒数第K个位置的节点

• 使用快慢指针：

ListNode slow = head, fast = head;
while (k-- > 0) fast = fast.next; // 这里会执行 K 次， 不确定也可以用 for-loop
while (fast != null) { // 这里的判断条件会让 fast 走到最后的null
    fast = fast.next;
    slow = slow.next;
}

• 快慢指针指向头，然后快指针先走K步，这样快慢指针间距就是K。然后快慢指针一起走，当快指针走到尾节点时，慢指针所在位置就是链表倒数第 K 位置。

链表声明：

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

解法一：快慢指针

• 虽然题目说的是旋转链表，但其实找到旋转后的链表的新头节点（倒数第 K 个位置）就可以了
• 这里要注意，题目给的 K 可能会超过链表的长度，也是官方设下的陷阱。所以一会要处理这个K
• 并且如果 K 是链表长度的整数倍，则翻转的结果与原链表没区别，直接返回。

public class Solution {
    
    // slow-fast two pointer to find k-th from the bottom
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        // judge k whether an integer multiple
        int sum = 0; // length of the List
        ListNode p = head;
        while (p != null) {
            p = p.next;
            sum++;
        }
        k %= sum;
        if (k == 0) return head;

        ListNode slow = head, fast = head;
        while (k-- > 0) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head; // location of fast pointer is at last of List
        return newHead;
    }

}

• k %= sum;是刚才说的处理K。也是实际上链表需要旋转的次数。
• while (fast.next != null)这里跟上面的准备工作里的找到倒数第K个节点不同，区别在于判断条件是 fast.next 。因为本题找到新头节点后，要让链表末尾节点连接到老头节点，然后让新头节点前的节点断链。所以实际上处理的是：倒数第K个节点的前一个节点。

解法二：闭环

• 官方解法，先把链表闭环，然后找到倒数第K个位置作为新头节点，同理。

public class Solution {

    // closed cycle and find k-th from the bottom
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) return head;
        // judge k whether an integer multiple
        int sum = 1;
        ListNode p = head;
        // judging condition is p.next in order to move p to the last node
        while (p.next != null) {
            p = p.next;
            sum++;
        }
        k %= sum;
        if (k == 0) return head;
        // closed cycle
        p.next = head;
        k = sum - k - 1;
        while (k-- > 0) head = head.next;
        ListNode newHead = head.next;
        head.next = null;
        return newHead;
    }

}

• 涉及到几个细节：
• 可以在统计链表长度的同时找到末尾节点，后面末尾节点连接到头节点形成闭环操作，复用指针p。所以这里统计长度又不同于解法一，sum初始化为1，while-loop判断对象为p.next，因为不能让p为null，后面会NPE。
• 处理完K之后，在闭环之后开始找到真正的位置，即sum - k - 1，-1 的目的同上，新头节点的前一个节点。
• 因为闭环的关系，所以不用特意去操作尾节点连到老头节点，直接断链返回就可以了。