algoadvance

Leetcode 61. Rotate List

Problem Statement

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

Example:

Clarifying Questions

  1. What is the expected output if k is 0?
    • The list should remain unchanged.
  2. What if the list is empty or has only one node?
    • For an empty list, return the empty list.
    • For a single-node list, return the list as is.
  3. Is k always a positive integer?
    • Not necessarily, k can be 0 or any non-negative integer.
  4. Should we consider very large values of k?
    • Yes, k can be larger than the length of the list, we will rotate it k % len(list) times as rotating a list with its length results in the same list.

Strategy

  1. Determine the length of the list.
    • Traverse the linked list to determine its length.
  2. Connect the list into a circular one.
    • By connecting the last node to the head, we form a circular list.
  3. Calculate the effective number of rotations needed.
    • Since rotating a list by its length results in the same list, the effective rotations needed can be found using k % length.
  4. Find the new tail and disconnect the circle.
    • The new tail will be at position length - (k % length) - 1.
    • The new head will be the node after the new tail.
  5. Disconnect the circle and set the next of the new tail to null.

Code

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class RotateList {
    public ListNode rotateRight(ListNode head, int k) {
        // Edge case: empty list
        if (head == null || head.next == null || k == 0) return head;

        // Determine the length of the list
        ListNode oldTail = head;
        int length = 1;
        while (oldTail.next != null) {
            oldTail = oldTail.next;
            length++;
        }

        // Create a circular list
        oldTail.next = head;

        // Effective rotations needed
        k = k % length;
        int newTailPos = length - k - 1;
        
        // Find the new tail
        ListNode newTail = head;
        for (int i = 0; i < newTailPos; i++) {
            newTail = newTail.next;
        }

        // Find the new head
        ListNode newHead = newTail.next;

        // Break the circle
        newTail.next = null;

        return newHead;
    }
}

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI