Problem

Given the head of a linked list, rotate the list to the right by k places.

Examples

Example 1:

1
2

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

1
2

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Solution

Method 1 - Iterative

Let’s take the linked list [1, 2, 3, 4, 5] as an example:

  1. Determine Length: First, calculate the length of the linked list (n). In this case, n = 5.
  2. Calculate Effective Rotations: Compute k % n to find the effective number of rotations needed. For instance, if k = 2, then 2 % 5 = 2.
  3. Traverse and Split: Traverse the list to the (n - k)th node and split the list into two parts. For k = 2, this means traversing (5 - 2) = 3 nodes, resulting in part1 = [1, 2, 3] and part2 = [4, 5].
  4. Reassemble the List: Concatenate the second part (part2) at the beginning of the first part (part1). The list now becomes [4, 5, 1, 2, 3].

Code

 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

public ListNode rotateRight(ListNode head, int k) {
        //for empty or list with 1 node return them as such         
        if(head == null || head.next == null || k == 0)
            return head;
        
        ListNode p = head;
		//length starts from 1 to include last element
        int len = 1; // note we are not setting to 0, but
        // as we want pointer to last element
        while(p.next!=null){
            p = p.next;
            len++;
        }
    
        k = k % len;
        if (k == 0){
            return head;
        }

		ListNode end = p;
		
        p = head;
        
        for(int i = 0;i<len-k-1;i++){
            p = p.next;
        }

        ListNode newHead = p.next;
        p.next = null;
        end.next = head;
        
        return newHead;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - Make a Cycle OR Circular Linkedlist

Same as previous solution, but we can make a cycle. Let’s take the linked list [1, 2, 3, 4, 5] as an example:

  1. Determine Length: Calculate the length of the linked list (n). In this case, n = 5.
  2. Create a Cycle: Connect the last node to the head to form a circular linked list.
  3. Calculate Effective Rotations: Compute k % n to determine the effective number of rotations needed. For example, if k = 2, then 2 % 5 = 2.
  4. Traverse and Split: Traverse the list from the head to the (n - k)th node, then split the list. For k = 2, this means traversing (5 - 2) = 3 nodes, resulting in list: [4, 5, 1, 2, 3]
  5. Make second part as first part: Make second part first, and first part second

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

public ListNode rotateRight(ListNode head, int k) {
    if(head == null || k == 0) {
        return head;
    }
    ListNode p = head;
    int len = 1;
    while(p.next != null) {
        p = p.next;
        len++;
    }
    p.next = head;// make it a circle here
    k %= len;
    for(int i = 0; i < len - k; i++) {
        p = p.next;
    }
    head = p.next;
    p.next = null;
    return head;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)