12-line fast python solution; O(n), one pass, 60ms


  • 0
    C
    def rotateRight(self, head, k):
        if not head or not head.next or k==0:
            return head
        tail, point, length = head, head, 1
        while point.next:
            if length > k:
                tail = tail.next
            length += 1
            point = point.next
        if k >= length:
            return self.rotateRight(head, k%length)
        newhead, point.next, tail.next = tail.next, head, None
        return newhead
    

    It's an O(n), one-pass solution if k < the length of the list.

    The idea is to use two pointers: one (point) goes through the whole list and another (tail) indicates the tail of the final rotated list. The initial position of tail is head. We only start updating tail when the current length > k so that the final distance between tail and point is k. After finishing the pass, we assign newhead to tail.next and then update everything accordingly.

    Example: 
    [1,2,3,4,5,6], k=2
    
    head        tail    point  #when the while loop ends
    [ 1,  2,  3,  4,  5,  6]  
                   newhead    
    #assign newhead, and then connect point to head, tail to None
    

    If eventually we find that k >= length (the total length is unknown until we finish the first pass!!!), we simply do it again with k%length. In this case, it's two passes but still O(n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.