题目

61. 旋转链表

题解

代码：

public class code61 {

    public static ListNode rotateRight(ListNode head, int k) {
        // base cases
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        // close the linked list into the ring
        ListNode old_tail = head;
        int n;
        for (n = 1; old_tail.next != null; n++) {
            old_tail = old_tail.next;
        }
        old_tail.next = head;

        // find new tail : (n - k % n - 1)th node
        // and new head : (n - k % n)th node
        ListNode new_tail = head;
        for (int i = 0; i < n - k % n - 1; i++) {
            new_tail = new_tail.next;
        }
        ListNode new_head = new_tail.next;

        // break the ring
        new_tail.next = null;

        return new_head;
    }

    public static ListNode createList_1() {
        ListNode head = new ListNode(1);
        ListNode cur = head;
        for (int i = 2; i <= 5; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }

    public static ListNode createList_2() {
        ListNode head = new ListNode(0);
        ListNode cur = head;
        for (int i = 1; i <= 2; i++) {
            cur.next = new ListNode(i);
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }

    public static void print(ListNode node) {
        if (node == null) {
            return;
        }
        ListNode current = node;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        ListNode head_1 = createList_1();
        print(head_1);
        int k_1 = 2;
        ListNode res_1 = rotateRight(head_1, k_1);
        print(res_1);

        System.out.println();

        ListNode head_2 = createList_2();
        print(head_2);
        int k_2 = 4;
        ListNode res_2 = rotateRight(head_2, k_2);
        print(res_2);
    }

}

参考：

1. 旋转链表——题解一
2. Leetcode 61:旋转链表（最详细解决方案！！！）——题解二
3. Rotate List （旋转链表，切断）——题解三