Rotate Linked List

Question#

Given the head node of a linked list, rotate the nodes around a specified pivot. This means to shift all elements following the pivot to the front of the linked list.

Example:

Original:
1 -> 2 -> 3 -> 4 -> 5
Pivot: 3
Result:
4 -> 5 -> 1 -> 2 -> 3

Implementation#

To rotate the linked list around a pivot, we need to modify some of the links. The tail of the linked list will now point to the head and the new head becomes the node after the pivot.

# pivot indicates the position to pivot at
def rotate(head, pivot):
p1 = head
p2 = head
prev = None
count = 0
# bring p1 and p2 to the pivot element
while p1 and count < pivot:
prev = p1
p1 = p1.next
p2 = p2.next
count += 1
p1 = prev
# bring p2 to the end
while p2:
prev = p2
p2 = p2.next
p2 = prev
# perform re-linking
p2.next = head
head = p1.next
p1.next = None