LeetCode.061.Rotate List 旋转链表

题目描述

61 Rotate List
https://leetcode-cn.com/problems/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

---

解题过程

旋转链表，或者叫 循环右移链表。
我的思路想的有点复杂了，先找到要右移的子链表的前一个结点p，然后把要移走的子链表反转后依次插入头部。
其实找到要右移的子链表的前一个结点p后，再进行2步就能完成，即把尾结点指向首结点，然后让p的下一个结点做新首节点。
但这个题最标准、最巧妙的做法是先把链表连成环，然后在 n-k 处断开环即可。
时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public ListNode rotateRight(ListNode head, int k) {
        if (null == head || null == head.next) {
            return head;
        }
        // 额外的头结点
        ListNode newHead = new ListNode(0);
        newHead.next = head;

        // 链表长度
        int length = 0;
        for (ListNode p = head; p != null; length++, p = p.next) {
        }
        // k对链表长度求余
        k = k % length;
        if (k == 0) {
            return head;
        }

        // cur 比 pre 先走 k 步
        ListNode pre = head, cur = head;
        for (int i = 0, j = 0; cur.next != null; i++, j++) {
            cur = cur.next;
            if (j >= k) {
                pre = pre.next;
            }
        }

        // pre 指向要移走的子链表的前一个结点
        // 把 pre 右侧的子链表逆置后再依次插入原链表头部即可
        ListNode reverseSubList = reverseList(pre.next);
        // pre是新结尾
        pre.next = null;
        for (ListNode p = reverseSubList; p != null;) {
            ListNode tempNext = p.next;
            p.next = newHead.next;
            newHead.next = p;
            p = tempNext;
        }

        return newHead.next;
    }

    // 递归反转链表，返回反转后链表的首结点
    private ListNode reverseList(ListNode head) {
        if (null == head || null == head.next) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_061_RotateList.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_061_RotateList.java

---