Rotate List Leetcode Problem 61 [Python Solution]

In this blog post, we're going to tackle the Rotate List problem on LeetCode.

This problem falls under the "Medium" difficulty category and is classified in the "Linked List" category.

We'll provide you with a detailed Python solution to this problem.

Let's get started!

Problem Overview

The problem statement is quite straightforward.

You are given the head of a linked list, and your task is to rotate the list to the right by k places.

Example 1:

Let's illustrate this with an example.

Suppose you have the input linked list as [1, 2, 3, 4, 5], and k is equal to 2.

The expected output should be [4, 5, 1, 2, 3].

Example 2:

Another example is when you have the input linked list as [0, 1, 2], and k is equal to 4.

In this case, the expected output is [2, 0, 1].

Understanding the Constraints

Before we dive into the solution, it's essential to understand the constraints that the problem presents.

• The number of nodes in the list is in the range [0, 500].
• The values of the nodes (Node.val) fall within the range [-100, 100].
• The value of k is in the range [0, 2 * 10^9].

Rotate List LeetCode Problem Solution

Now, let's take a look at the Python solution to this problem.

We'll provide both a brute force approach and a more efficient solution.

1. Bruteforce Approach

First, we will take a brute force approach to understand the problem more clearly.

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head

    old_head = head

    curr, size = head, 0
    while curr:
        curr, size = curr.next, size + 1

    if k % size == 0:
        return head

    k %= size
    slow = fast = head
    while fast and fast.next:
        if k <= 0:
            slow = slow.next
        fast = fast.next
        k -= 1

    new_tail, new_head, old_tail = slow, slow.next, fast
    new_tail.next, old_tail.next = None, old_head

    return new_head

2. An Efficient Approach

Now, let's look at a more efficient solution.

def rotateRight(head, k):
    if not head or not head.next or k == 0:
        return head

    length = 1
    tail = head

    while tail.next:
        tail = tail.next
        length += 1

    k %= length

    if k == 0:
        return head

    tail.next = head
    for _ in range(length - k):
        tail = tail.next

    new_head = tail.next
    tail.next = None

    return new_head

This efficient approach minimizes the number of iterations and handles edge cases effectively.

Time and Space Complexity

Time Complexity: The efficient approach has a time complexity of O(n), where n is the number of nodes in the linked list.

This is because we traverse the entire linked list once to find its length and perform the rotation in a single pass.

Space Complexity: The space complexity is O(1) for both the brute force and efficient solutions.

We only use a constant amount of extra space for variables.

Reasoning Behind Our Approach

Our approach works as follows:

1. We first check for edge cases.

If the linked list is empty or has only one node, or if k is zero, we return the list as it is.

1. We traverse the linked list to find its length and update the tail pointer to point to the last node.

This is done to calculate the effective value of k by taking its modulus with the length.

1. If k becomes zero after taking the modulus, we return the list as it is since there's no need for rotation.

2. We then perform the rotation as follows:

   • We connect the original tail node to the original head node, effectively making the list circular.
   • We move tail to the appropriate position for the rotation.
   • We update the new_head to the node after tail, and set tail.next to None to break the circularity.
   • Finally, we return the new_head.

This approach ensures that we perform the rotation efficiently and handle edge cases correctly.

Related Interview Questions By Company:

• Subsets LeetCode
• Asteroid Collision LeetCode
• Combination Sum II LeetCode

Related Interview Questions By Difficulty:

• Copy List With Random Pointer LeetCode
• Reverse Nodes In K Group LeetCode
• Design Browser History LeetCode

Related Interview Questions By Category:

• Seat Reservation Manager LeetCode
• Shift 2D Grid LeetCode
• Merge Two Binary Trees LeetCode

Conclusion

In this blog post, we tackled the Rotate List problem on LeetCode.

We provided both a brute force and an efficient Python solution for this problem.

Understanding the problem's constraints and edge cases is crucial, and we demonstrated how to address them in the code.

If you found this blog post helpful, please like and engage to support our content.

Feel free to ask questions, make suggestions, and share this content with others who might find it useful.

Question Link

Thank you for reading, and we hope you continue to explore more coding challenges and solutions!