61. Rotate List 「旋转链表」

给定一个链表,向右旋转链表 k 次,k 大于等于 0。

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

例二:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释: 向右旋转一次:2->0->1->NULL,向右旋转两次:1->2->0->NULL,向右旋转三次:0->1->2->NULL,向右旋转四次:2->0->1->NULL

/*
 * 61. Rotate List
 * https://leetcode.com/problems/rotate-list/
 * https://www.whosneo.com/61-rotate-list/
 */

class RotateList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        RotateList solution = new RotateList();

        solution.print(head);
        System.out.println("Rotate 1");
        head = solution.rotateRight(head, 1);
        solution.print(head);
        System.out.println("Rotate 1");
        head = solution.rotateRight(head, 1);
        solution.print(head);
        System.out.println("Rotate 3");
        head = solution.rotateRight(head, 3);
        solution.print(head);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    private ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null)
            return head;
        ListNode node = head;
        int length = 1;
        while (node.next != null) {
            node = node.next;
            length++;
        }
        k = k % length;
        k = length - k; //值的范围 [1, length],表示要进行移动的次数
        //循环链表
        node.next = head;
        while (k > 0) {
            head = head.next;
            node = node.next;
            k--;
        }
        node.next = null;
        return head;
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注