[Coderust] Rotate List

 

 

Problem

 

 

 

---

 

Solution

 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head
        
        # need to know "k % length of list" to find the point of rotation
        # go to the end of the list while counting length
        lptr = head
        l = 1
        while lptr.next:
            l += 1
            lptr = lptr.next
        
        # find where to cut the list (the node before new head)
        n = l-(k % l)-1
        
        # rotated list is same as the original if n = l-1
        if n == l-1:
            return head
        
        dummy = head
        for _ in range(n):
            dummy = dummy.next
        
        # cut the list, connect the end of original list to the head of original list
        new_h = dummy.next
        dummy.next = None
        lptr.next = head
        
        return new_h

 

Time Complexity

O(N)

 

 

Space Complexity

O(1)