/ Data Structure and Algorithms  

Leetcode 61. Rotate List

Question



Move the last linked list node to the front and repeat the process k times.

Similar Questions

Solution

Obviously we don’t really need to move nodes one by one. If the length of the linked list is len and n = k % len, we only need to move the last n nodes to the front. We only need to find the pointer of the inverse n + 1 node and point it to null, and the pointer at the end to the head node. Finding the last n nodes reminds me of 19. Remove Nth Node From End of List, using the fast and slow pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static ListNode rotateRight(ListNode head, int k) {
    // length of the list
    int length = 1;
    ListNode node = head;

    if (head == null) {
        return null;
    }

    // get length of the list
    while (node.next != null) {
        node = node.next;
        length++;
    }

    ListNode tail;

    // now 'node' is the last node in the last
    // connect tail to head
    node.next = head;
    tail = node;

    // Move right k place = moving head to right by (length - k % length) places
    int steps = length - k % length;

    while (steps > 0) {
        head = head.next;
        tail = tail.next;

        steps--;
    }

    tail.next = null;

    return head;
}

Time complexity O(n).

Space complexity O(1).