Skip to content

61. Rotate List

Linked List Two Pointers

Problem - Rotate List

Medium

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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

        current, n = head, 0
        while current:
            n += 1
            current = current.next

        k %= n
        if k == 0:
            return head

        fast = slow = head
        for _ in range(k):
            fast = fast.next
        while fast.next:
            fast, slow = fast.next, slow.next

        result = slow.next
        slow.next = None
        fast.next = head
        return result

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 17.8 MB (85.60%)