Leetcode: Rotate List
Rotate a singly-linked list at k elements from their end.
The two tricks here are to use a slower running pointer and detect if i < k when the end is reached.
If that is the case, k is greater than the list and we can take the modulo, then iterating once more
over the list. This is more efficient than to iterate n times over the large list in a circle.
# 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 head is None or head.next is None:
return head
# find k-th element
# If list smaller than k, take modulo
# Else take k
# Find length of list
curr = head
new_head = head
i = 0
while curr.next is not None:
curr = curr.next
if i >= k:
new_head = new_head.next
i += 1
if i >= k:
# k is less than length of list
pass
else:
# k is greater than length of list
new_k = k % (i + 1)
curr = head
new_head = head
i = 0
while curr.next is not None:
curr = curr.next
if i >= new_k:
new_head = new_head.next
i += 1
curr.next = head
head = new_head.next
new_head.next = None
return head