[Top Interview 150] 61. Rotate List

Solution)

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # Base Case
        if not head: return None
        
        # Two Pointers
        slow, fast = head, head

        # Find length and send fast to the end of the list
        length = 1
        while fast.next:
            fast = fast.next
            length += 1
        fast.next = head

        # Reduce k and move slow
        k %= length
        for i in range(length-k-1):
            slow = slow.next
        
        # Connect necessary nodes
        ans = slow.next
        slow.next = None
        
        return ans

 
Problem: LeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)

* n = number of nodes
 

Explanation)

We'll look for the last k nodes from the list and bring those last nodes to the front of the list.
 
What if k is longer than the length of the list?
We can adjust k by finding the remainder when dividing k by the length of the list.
 
Now let's see how to code this.

 

1. Base Case & Two Pointers)

As usual, if there isn't a node, we'll return None no matter how big k is.
 
The two pointers slow and fast indicate the start and the tail of the last k nodes.
 

Wanted positions of slow and fast

 

def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 1. Base Case and Two Pointers
        if not head: return None
        
        slow, fast = head, head

 

2. Find the length of list and connect tail to head)

While sending fast to the end of the list, we can use this to count the number of nodes.

 

We send fast to the end, because we know that's the position of tail of last k nodes.
 
After finding the length, we'll connect fast to head.
We do this to easily disconnect nodes and return rotated list.  
 

def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 1. Base Case and Two Pointers
        if not head: return None
        
        slow, fast = head, head

        # 2. Find the length of list and connect tail to head
        length = 1
        while fast.next:
            fast = fast.next
            length += 1
        fast.next = head

 

3. Adjust k and move slow)

We adjust k so that we don't need to keep rotating the same sequence. It's a lot efficient than rotating 2000000000 times.
 
Once we have the adjusted k, we need to move slow to its proper position.
Now we have slow and fast in their needed positions.
 

def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 1. Base Case and Two Pointers

        # 2. Find the length of list and connect tail to head
        length = 1
        while fast.next:
            fast = fast.next
            length += 1
        fast.next = head
        
        # 3. Adjust k and move slow
        k %= length
        for i in range(length-k-1):
            slow = slow.next

 

4. Disconnect the part so we have the properly rotated list)

We need to cut the link between slow and slow.next.
 

Disconnecting the link

 

def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 1. Base Case and Two Pointers
        # 2. Find the length of list and connect tail to head
        
        # 3. Adjust k and move slow
        k %= length
        for i in range(length-k-1):
            slow = slow.next
            
        # 4. Disconnect the part so we have the properly rotated list 
        ans = slow.next
        slow.next = None
        
        return ans

 
 
 
I first had a solution very similar to this but was too messy. So I looked at other solutions and this had clean details that my solution was missing. I can come up with proper logics now but still have a hard time making the codes clean. Linked lists always make my brain numb.