61. Rotate List

MediumLinked ListTwo Pointers
Leetcode Link

Problem Description

The problem presents a singly linked list and an integer k. The task is to move the last k nodes of the list to the front, essentially rotating the list to the right by k places. If the list has n nodes and k is greater than n, the rotation should be effective after k modulo n moves. If a list is empty or has a single node, it remains unchanged after rotation.

Intuition

To address this problem, we can follow a series of logical steps:

  1. Determine the length of the list. This helps to understand how many rotations actually need to be performed since rotating a list by its length n, or multiples of n, results in the same list.

  2. Since rotating by k places where k is greater than the length of the list (let's call it n) is the same as rotating by k modulo n places, we calculate k %= n. This simplifies the problem by ensuring that we don't perform unnecessary rotations.

  3. Identify the k-th node from the end (or (n - k)-th from the beginning after adjusting k) which after rotation will become the new head of the list. We use two pointers, fast and slow. We initially set both to the head of the list and move fast k steps forward.

  4. We then advance both fast and slow pointers until fast reaches the end of the list. At this point, slow will be pointing to the node right before the k-th node from the end.

  5. We update the pointers such that fast's next points to the old head, making the old tail the new neighbor of the old head. The slow's next becomes the new head of the rotated list, and we also need to set slow's next to None to indicate the new end of the list.

Following this approach leads us to the rotated list which is required by the problem.

Learn more about Linked List and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Solution Approach

The implementation of the solution uses the two-pointer technique along with an understanding of [linked list](/problems/linked_list_cycle) traversal to achieve the rotation. Here is the step-by-step walk-through:

  1. Check for Edge Cases: If the head of the list is None or if there is only one node (head.next is None), there is nothing to rotate, so we simply return the head.

  2. Calculate the Length (n): We traverse the entire list to count the number of nodes, storing this count in n. This traversal is done using a while loop that continues until the current node (cur) is None.

  3. Adjust k by Modulo: Since rotating the list n times results in the same list, we can reduce k by taking k modulo n (k %= n). This simplifies the number of rotations needed to the minimum effective amount.

  4. Early Exit for k = 0: If k becomes 0 after the modulo operation, this means the list should not be rotated as it would remain the same. Thus, we can return the head without any modifications.

  5. Initialize Two Pointers: Start with two pointers, fast and slow, both referencing the head of the list. These pointers are going to help us find the new head after the rotations.

  6. Move Fast Pointer: Forward the fast pointer by k steps. Doing this will place fast exactly k nodes ahead of slow in the list.

  7. Move Both Pointers Until Fast Reaches the End: Now, move both fast and slow pointers simultaneously one step at a time until fast is at the last node of the list. Due to the initial k steps taken, slow will now be pointing to the (n-k-1)-th node or the one right before the new head of the rotated list.

  8. Perform the Rotation:

    • The node following slow (slow.next) is the new head of the rotated list (ans).
    • To complete the rotation, we set the next node of the current last node (fast.next) to the old head (head).
    • To mark the new end of the list, we assign None to the next of slow (slow.next = None).

By following the above steps, we have rotated the list to the right by k places effectively and efficiently. As a result, the ans pointer, now referring to the new head of the list, is then returned as the final rotated list.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Example Walkthrough

Let's illustrate the solution approach with a small example:

Suppose we have a linked list [1 -> 2 -> 3 -> 4 -> 5] and we are given k = 2.

  1. Check for Edge Cases: The list is not empty and has more than one node, so we can proceed.

  2. Calculate the Length (n): By traversing the list, we determine the length n = 5.

  3. Adjust k by Modulo: Since k = 2 is not greater than n, k % n is still k. Thus, k remains 2.

  4. Early Exit for k = 0: k is not 0, so we do need to perform a rotation.

  5. Initialize Two Pointers: We set both fast and slow to the head of the list. Currently, fast and slow are pointing to 1.

  6. Move Fast Pointer: We advance fast by k steps: from 1 to 2, then 2 to 3. Now, fast is pointing to 3, and slow is still at 1.

  7. Move Both Pointers Until Fast Reaches the End: We advance both pointers until fast is at the last node:

    • Move slow to 2 and fast to 4.
    • Move slow to 3 and fast to 5.
    • Now fast is at 5, the end of the list, and slow is at 3.

  8. Perform the Rotation:

    • The node after slow (slow.next), which is 4, will become the new head.
    • We set fast.next (which is 5.next) to the old head (1), forming a connection from 5 to 1.
    • We update slow.next to None to indicate the new end of the list.

After performing rotation, the list now becomes [4 -> 5 -> 1 -> 2 -> 3] because the last two nodes (4 and 5) have been moved to the front of the list.

By returning the new head (4 in this case), we conclude the rotation process and the modified list is correctly rotated by k places.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next=None):
4        self.val = val
5        self.next = next
6
7class Solution:
8    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
9        # If the list is empty or has just one element, no rotation is needed
10        if head is None or head.next is None:
11            return head
12      
13        # Count the number of elements in the linked list
14        current, length = head, 0
15        while current:
16            length += 1
17            current = current.next
18
19        # Compute the actual number of rotations needed as k could be larger than the length of the list
20        k %= length
21        if k == 0:  # If no rotation is needed
22            return head
23
24        # Use two pointers, fast and slow. Start both at the beginning of the list
25        fast = slow = head
26      
27        # Move the fast pointer k steps ahead
28        for _ in range(k):
29            fast = fast.next
30      
31        # Move both pointers at the same speed until fast reaches the end of the list
32        while fast.next:
33            fast, slow = fast.next, slow.next
34      
35        # At this point, slow is at the node before the new head after rotation
36        # We can now adjust the pointers to complete the rotation
37        new_head = slow.next
38        slow.next = None  # The next pointer of the new tail should point to None
39        fast.next = head  # The next pointer of the old tail should point to the old head
40      
41        return new_head  # Return the new head of the list
42
43# Note: The Optional[ListNode] type hint should be imported from typing 
44# if you want to use it for type checking in Python 3.
45# Otherwise, you can omit it from the function signatures.
46
1// Definition for singly-linked list.
2class ListNode {
3    int val;
4    ListNode next;
5    ListNode() {}
6    ListNode(int val) { this.val = val; }
7    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
8}
9
10class Solution {
11    public ListNode rotateRight(ListNode head, int k) {
12        // If the list is empty or has one node, no rotation needed
13        if (head == null || head.next == null) {
14            return head;
15        }
16
17        // Find the length of the linked list
18        ListNode current = head;
19        int length = 0;
20        while (current != null) {
21            length++;
22            current = current.next;
23        }
24
25        // Normalize k in case it's larger than the list's length
26        k %= length;
27      
28        // If k is 0, the list remains unchanged
29        if (k == 0) {
30            return head;
31        }
32
33        // Use two pointers: 'fast' will lead 'slow' by 'k' nodes
34        ListNode fast = head;
35        ListNode slow = head;
36        while (k > 0) {
37            fast = fast.next;
38            k--;
39        }
40
41        // Move both at the same pace. When 'fast' reaches the end, 'slow' will be at the k-th node from the end
42        while (fast.next != null) {
43            fast = fast.next;
44            slow = slow.next;
45        }
46
47        // 'slow' is now at the node after which the rotation will occur
48        ListNode newHead = slow.next;
49      
50        // Break the list at the node 'slow' and make 'fast' point to the original head to rotate
51        slow.next = null;
52        fast.next = head;
53
54        // Return the new head of the rotated list
55        return newHead;
56    }
57}
58
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* rotateRight(ListNode* head, int k) {
14        // If the head is null or there is only one node, return the head as rotation isn't needed
15        if (!head || !head->next) {
16            return head;
17        }
18
19        // find the length of the linked list
20        ListNode* current = head;
21        int length = 0;
22        while (current) {
23            ++length;
24            current = current->next;
25        }
26
27        // Normalize k to prevent unnecessary rotations if k >= length
28        k %= length;
29      
30        // If k is 0 after modulo operation, no rotation is needed; return the original head
31        if (k == 0) {
32            return head;
33        }
34
35        // Set two pointers, fast and slow initially at head
36        ListNode* fast = head;
37        ListNode* slow = head;
38
39        // Move fast pointer k steps ahead
40        while (k--) {
41            fast = fast->next;
42        }
43
44        // Move both slow and fast pointers until fast reaches the end of the list
45        while (fast->next) {
46            fast = fast->next;
47            slow = slow->next;
48        }
49
50        // The slow pointer now points to the node just before rotation point
51        // The fast pointer points to the last node of the list
52        ListNode* newHead = slow->next; // This will be the new head after rotation
53        slow->next = nullptr; // Break the chain to form a new end of the list
54        fast->next = head; // Connect the original end of the list to the original head
55
56        // Return the new head of the rotated list
57        return newHead;
58    }
59};
60
1// Definition for singly-linked list.
2class ListNode {
3    val: number;
4    next: ListNode | null;
5    constructor(val: number = 0, next: ListNode | null = null) {
6        this.val = val;
7        this.next = next;
8    }
9}
10
11/**
12 * Rotates the list to the right by k places.
13 *
14 * @param {ListNode | null} head - The head of the linked list.
15 * @param {number} k - Number of places to rotate the list.
16 * @return {ListNode | null} - The head of the rotated linked list.
17 */
18function rotateRight(head: ListNode | null, k: number): ListNode | null {
19    // If the head is null or there is only one node, return the head as no rotation is needed.
20    if (!head || !head.next) {
21        return head;
22    }
23
24    // Find the length of the linked list.
25    let current: ListNode | null = head;
26    let length: number = 0;
27    while (current) {
28        length++;
29        current = current.next;
30    }
31
32    // Normalize k to prevent unnecessary rotations if k is greater than or equal to length.
33    k %= length;
34  
35    // If k is 0 after the modulo operation, no rotation is needed; return the original head.
36    if (k === 0) {
37        return head;
38    }
39
40    // Set two pointers, fast and slow, initially at the head.
41    let fast: ListNode = head;
42    let slow: ListNode = head;
43
44    // Move the fast pointer k steps ahead.
45    while (k > 0) {
46        fast = fast.next!;
47        k--;
48    }
49
50    // Move both slow and fast pointers until the fast reaches the end of the list.
51    while (fast.next) {
52        fast = fast.next;
53        slow = slow.next!;
54    }
55
56    // The slow pointer now points to the node just before the rotation point.
57    // The fast pointer points to the last node in the list.
58    let newHead = slow.next; // This will be the new head after rotation.
59    slow.next = null; // Break the chain to form a new end of the list.
60    fast.next = head; // Connect the original end of the list to the original head.
61
62    // Return the new head of the rotated list.
63    return newHead;
64}
65
Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

Time Complexity

The time complexity of the given Python code can be broken down into the following steps:

  1. Iterate through the linked list to find out the length n: This process takes O(n) time as it goes through all elements of the linked list exactly once.

  2. Calculate k %= n: This calculation is done in constant time, O(1).

  3. Moving the fast pointer k steps ahead: This again takes O(k) time, but since k in this case is always less than n after the modulo operation, we can say this operation takes at most O(n) time.

  4. Moving both fast and slow pointers to find the new head of the rotated list: This has to traverse the remainder of the list, which takes at most O(n-k) time. However, in worst-case scenarios where k is 0, this would result in O(n) time. Since the previous steps ensure that k < n, the combined operations will still be O(n).

  5. Re-link the end of the list to the previous head and set the next of the new tail to None: These operations are done in constant time, O(1).

In all, considering that O(n) is the dominating factor, the overall time complexity of the code is O(n).

Space Complexity

The space complexity of the code can also be analyzed:

  1. The given algorithm only uses a fixed amount of extra space for variables cur, n, fast, and slow, regardless of the size of the input linked list.

  2. No additional data structures are used that depend on the size of the input.

  3. All pointer moves and assignments are done in-place.

Hence, the space complexity is O(1), which means it requires constant extra space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫