Given the head of a linked list, rotate the list to the right by k places.
Example 1:
Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]
Example 2:
Input: head = [0,1,2], k = 4 Output: [2,0,1]
Constraints:
The number of nodes in the list is in the range [0, 500].
-100 <= Node.val <= 100
0 <= k <= 2 * 109
- code
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return None
run_count = head
count = 1
while run_count and run_count.next:
run_count = run_count.next
count += 1
last = run_count
if k % count == 0:
return head
first_half_count = count - k % count - 1
run_count = head
while first_half_count:
run_count = run_count.next
first_half_count -= 1
new_head = run_count.next
run_count.next = None
last.next = head
return new_head
- code
class Solution:
def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':
# base cases
if not head:
return None
# close the linked list into the ring
old_tail = head
n = 1
while old_tail.next:
old_tail = old_tail.next
n += 1
old_tail.next = head
# find new tail : (n - k % n - 1)th node
# and new head : (n - k % n)th node
new_tail = head
for i in range(n - k % n - 1):
new_tail = new_tail.next
new_head = new_tail.next
# break the ring
new_tail.next = None
return new_head