0061-rotate-list¶

Description¶

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 * 10⁹

Solution(Python)¶

# 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: ListNode | None, k: int) -> ListNode | None:
        # 1 2 3 4 5
        # 5 -> 1 ... 4
        # 4..5 -> 1 ..3 
        # n -> length of linkedlist 5
        # k = 2
        # n- k = 3
        #  00....n-k  n-k + 1 ...n
        # 1 2 3 4 5
        # 1 2 3
        # new head => n-k+1 
        #  1......n
        #  0......n-1
        #  0....n-k-1 
        if not head or k == 0:
            return head
        n,tail = 1, head
        while tail.next:
            tail = tail.next
            n+=1
        k %= n
        tail.next = head
        cur= head
        for _ in range(n-k - 1):
            cur = cur.next
        newhead = cur.next
        cur.next  = None
        return newhead
        

        