61. Rotate List

Problem Statement

link: https://leetcode.com/problems/rotate-list/description/ https://leetcode.cn/problems/rotate-list/description/

Given the head of a linked list, rotate the list to the right by k places.

Example:

Input: head = [1,2,3,4,5], k = 2 Output: [4,5,1,2,3]

Input: head = [0,1,2], k = 4 Output: [2,0,1]

Solution Approach

The solution connects the tail of the list to the head, forming a circular linked list, and then repositions the head to a new node after k rotations.

Algorithm

1. Traverse the list to determine its length and make it a circular linked list by connecting the tail to the head.
2. Compute the position of the new head by calculating the remainder of k divided by the list length.
3. Move to the determined position, sever the circular connection, and return the new head.

Implement

    class Solution:
      def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
          if not head or not head.next:
              return head
          # connect
          tmp = head
          l = 1
          while tmp.next:
              tmp = tmp.next
              l += 1
          tmp.next = head
          #count the length from head to new_end
          new_end = head
          steps_move = l - k % l # module
          for _ in range(steps_move - 1):
              new_end = new_end.next
          #cut the head and end
          head = new_end.next
          new_end.next = None
          return head
      

    
    

Twitter  facebook  Email