单链表旋转

[geosmart]

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

算法步骤

旋转链表

1. 求链表长度
2. 计算实际需要移动的位置k
3. 快慢指针法找到倒数第k个节点
4. 链表旋转：k节点作为新的链表头，k-1节点作为链表尾，中间部分以循环链表方式连接

复杂度

• 空间复杂度：O(1)
• 时间复杂度：O(n)

代码实现

版本1

public static ListNode rotateRight(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode tmp = dummy.next;
        int n = 0;
        //求链表长度
        while (tmp != null) {
            tmp = tmp.next;
            n++;
        }
        if (n == 0 || k % n == 0) {
            return dummy.next;
        }
        //当成循环链表，n次移动等于没移动，求余后的k为实际需移动的位置数
        k = k % n;
        //快慢指针求倒数第k个节点
        ListNode slow = dummy;
        ListNode fast = dummy;
        while (k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //kNode为返回结果的head
        ListNode kNode = slow.next;
        //原slow节点即为tail
        slow.next = null;
        //连接原链表的头部
        fast.next = head;
        return kNode;
    }

版本2：快慢指针法，关键是k = k % n

public static ListNode rotateRight(ListNode head, int k) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy.next;
        int n = 1;
        //快指针，求链表长度和tail节点
        while (fast.next != null) {
            fast = fast.next;
            n++;
        }
        //n次移动等于没移动
        if (k % n == 0) {
            return dummy.next;
        }
        //当成循环链表，求余后的k为实际需移动的位置数
        k = k % n;
        ListNode slow = dummy.next;
        //求倒数第k个节点
        for (int i = 0; i < n - k - 1; i++) {
            slow = slow.next;
        }
        ListNode newHead = slow.next;
        slow.next = null;
        //连接原链表的头部
        fast.next = head;
        return newHead;
    }