We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rotate List

Number: 61

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Meta, LinkedIn, Amazon, Microsoft, Oracle, Siemens, Adobe, Apple, Infosys

Problem Description

Given the head of a singly-linked list, rotate the list to the right by k places. This means moving the last k nodes to the front of the list while preserving the order of the remaining nodes.

Key Insights

  • Calculate the length of the list and locate the tail.
  • Use k modulo length to handle rotations greater than the list size.
  • Find the new tail of the list at position (length - k - 1) and update pointers accordingly.
  • Link the original tail to the original head to form a circular list, then break the circle at the new tail.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the list, since we traverse the list a few times. Space Complexity: O(1), as the rotation is done in place without extra data structures.

Solution

We first traverse the list to determine its length and identify the tail node. The effective rotation is calculated by taking k modulo the length of the list. If the result is zero, the list remains unchanged. Otherwise, we locate the new tail node by moving (length - k - 1) steps from the head. The node after the new tail becomes the new head. Finally, we break the link after the new tail and connect the old tail to the original head to finalize the rotated list.

Code Solutions

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:  # Check if rotation is necessary
            return head
        
        # Compute the length of the list and locate the tail node
        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1
        
        # Calculate the effective number of rotations
        k = k % length
        if k == 0:
            return head
        
        # Find the new tail: (length - k - 1) steps from the head
        stepsToNewTail = length - k - 1
        newTail = head
        for _ in range(stepsToNewTail):
            newTail = newTail.next
        
        # Set the new head and break the list
        newHead = newTail.next
        newTail.next = None
        
        # Connect the old tail to the original head
        tail.next = head
        
        return newHead
← Back to All Questions