【双指针】旋转链表

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

示例 1:

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-list

AC代码

public ListNode rotateRight(ListNode head, int k) {
    if (null == head || k == 0) {
        return null;
    }

    // 定义left、right双指针
    ListNode left = head;
    ListNode right = head;

    // right指针先走k步
    for (int i = 1; i <= k; i++) {
        // 如果没走完k步，发现right.next为null，说明链表长度小于k，且链表长度为i
        // 把k设为k % i，right指针重新走k步
        if (null == right.next) {
            k %= i;
            // k为0，说明k是链表长度的倍数，直接返回head
            if (k == 0) {
                return head;
            }
            right = head;
            for (int j = 1; j <= k; j++) {
                right = right.next;
            }
            break;
        }
        right = right.next;
    }

    // 双指针同时走，直到right.next为null，即right指向最后一个节点
    // 此时left指针后刚好有k个节点，因为right指针提前走了k步
    while (right.next != null) {
        left = left.next;
        right = right.next;
    }

    // 把left指针之前的节点（包含left指向的节点）移到right节点后面
    ListNode newHead = left.next;
    right.next = head;
    left.next = null;

    return newHead;
}

image.png