Rotate List

 

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

Example:

python
# Example usage of the function
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
k = 2
rotated_head = rotateRight(head, k)
# The list 1 -> 2 -> 3 -> 4 -> 5 after rotating by 2 places to the right becomes 4 -> 5 -> 1 -> 2 -> 3

1. Clarify the problem: Before starting, let's ask some clarifying questions to ensure we fully understand the problem requirements:

  • Can the given linked list be empty?
  • Can the value of k be greater than the length of the linked list?
  • What should be the behavior if k is 0 or negative?

2. Analyze the problem: Let's break down the problem to better understand its components:

  • Input: The head of a linked list and an integer k.
  • Output: The head of the rotated linked list.
  • Constraints: The length of the linked list is in the range [0, 5000], and k is a non-negative integer.

3. Design an algorithm: To rotate the linked list to the right by k places, we need to perform the following steps:

  1. Count the length of the linked list.
  2. Calculate the effective value of k by taking its modulo with the length of the linked list.
  3. If the effective value of k is 0, return the original head of the linked list since no rotation is needed.
  4. Find the new tail of the rotated linked list by traversing to the (length - effective k)th node.
  5. Update the pointers to rotate the list: set the new tail's next node as the new head and set the node before the new tail as None.
  6. Return the new head of the rotated linked list.

4. Explain your approach: We will count the length of the linked list and calculate the effective value of k by taking its modulo with the length. If the effective value of k is 0, no rotation is needed, so we return the original head. Otherwise, we find the new tail of the rotated list and update the pointers accordingly to rotate the list. Finally, we return the new head of the rotated linked list.

5. Write clean and readable code:

Here's an implementation of the algorithm in Python:

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def rotateRight(head, k):
    if not head:
        return None

    # Count the length of the linked list
    length = 1
    curr = head
    while curr.next:
        curr = curr.next
        length += 1

    # Calculate the effective value of k
    k = k % length
    if k == 0:
        return head

    # Find the new tail and update the pointers
    new_tail = head
    for _ in range(length - k - 1):
        new_tail = new_tail.next

    new_head = new_tail.next
    new_tail.next = None
    curr.next = head

    return new_head

6. Test your code: Now, let's test the code with the example usage and some additional test cases:

python
# Example test case
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
k = 2
rotated_head = rotateRight(head, k)
# The list 1 -> 2 -> 3 -> 4 -> 5 after rotating by 2 places to the right becomes 4 -> 5 -> 1 -> 2 -> 3

# Additional test cases
# Test case 1: Empty list
head = None
k = 3
rotated_head = rotateRight(head, k)
# Expected output: None

# Test case 2: Rotating by 0 places
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
k = 0
rotated_head = rotateRight(head, k)
# Expected output: 1 -> 2 -> 3

# Test case 3: Rotating by a value greater than the length of the list
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
k = 5
rotated_head = rotateRight(head, k)
# Expected output: 2 -> 3 -> 1

# Test case 4: Rotating by the length of the list
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
k = 3
rotated_head = rotateRight(head, k)
# Expected output: 1 -> 2 -> 3

# Test case 5: Large input
head = ListNode(1)
curr = head
for i in range(2, 5001):
    curr.next = ListNode(i)
    curr = curr.next
k = 10000
rotated_head = rotateRight(head, k)
# Expected output: 5000 -> 1 -> 2 -> 3 -> ... -> 4999

7. Optimize if necessary: The implemented algorithm has a time complexity of O(n) since we need to traverse the linked list to count its length and find the new tail. This is already an optimal solution for the problem, so there is no further optimization required.

8. Handle error cases: The given code handles the case of an empty linked list by returning None. It assumes that the value of k is a non-negative integer. Error handling strategies can be discussed with the interviewer.

9. Discuss complexity analysis:

  • Time complexity: The algorithm has a time complexity of O(n), where n is the length of the linked list. This is because we need to traverse the linked list to count its length and find the new tail.
  • Space complexity: The space complexity is O(1) since the algorithm uses a constant amount of extra space to store variables and update the pointers.
Next Post Previous Post