61.旋转链表

目标

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4
输出：[2,0,1]

说明：

• 链表中节点的数目在范围 [0, 500] 内
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 10^9

思路

将链表的每个节点右移 k 个位置，即将链表最后 k % list.size() 个元素放到列表头。

可以使用快慢指针，slow 指向最后 k 个节点的前面一个节点，slow 指针移到到 fast 指针需要移动 k + 1 次，即后面 k 个节点和 null。先让 fast 移动 k + 1 次，再让 slow 与 fast 同时移动。

代码

/**
 * @date 2024-11-24 16:15
 */
public class RotateRight61 {

    public ListNode rotateRight_v1(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int length = 1;
        ListNode last = head;
        while (last.next != null) {
            last = last.next;
            length++;
        }
        k = k % length + 1;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null) {
            fast = fast.next;
            k--;
            if (k < 0) {
                slow = slow.next;
            }
        }
        last.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }

}

性能