Pattern visualizer
Rotate List
Rotating right by k moves the last k nodes to the front. Doing that one node at a time costs a full scan per rotation, and k can be far larger than the list. Instead, walk once to the last node while counting the length n, then link that last node back to the head. The list is now a ring, and every rotation of a ring is the same ring — only the place it is cut open differs. Reduce k to k MOD n, walk n - k - 1 steps from the head to the new tail, take its next as the new head, and break the ring there. Two partial passes, constant extra space, and k's size never matters. Animated on: list = [1,2,3,4,5], k=2. Rotate the list to the right by k places. Answer: [4,5,1,2,3]..
Close the list into a ring, then cut it at n - k MOD n
list = [1,2,3,4,5], k=2. A singly-linked list has no length field, so the first job is to walk to the last node and count on the way: n <- 1 at the head. The last node is needed anyway, because rotation reconnects it to the head.
1FUNCTION rotateRight(head, k)2 IF head = NULL RETURN head3 n <- 1, tail <- head4 WHILE tail.next != NULL5 tail <- tail.next6 n <- n + 17 k <- k MOD n8 IF k = 0 RETURN head9 tail.next <- head10 newTail <- head11 FOR i <- 1 TO n - k - 112 newTail <- newTail.next13 head <- newTail.next14 newTail.next <- NULL15 RETURN head
← / → step · space play · Home restart