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
k. After finishing the pass, we assign
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).