Solving Rotate List in JavaScript: Step-by-Step Guide

Introduction to Rotate List

The "Rotate List" problem is a classic algorithmic challenge frequently encountered in coding interviews and competitive programming. At its core, the problem asks you to take a singly linked list and rotate it to the right by a given number of positions. While the concept sounds simple, implementing an efficient solution requires a solid understanding of linked list traversal, edge case handling, and pointer manipulation.

In this tutorial, we will walk through the problem step by step, explore multiple approaches, and discuss best practices to help you write clean, efficient, and interview-ready JavaScript code.

What Is the Rotate List Problem?

Given the head of a singly linked list and an integer k, rotate the list to the right by k places. Rotating to the right means that the last k nodes are moved to the front of the list.

Example

Consider the linked list: 1 -> 2 -> 3 -> 4 -> 5 and k = 2.

After rotating right by 2, the list becomes: 4 -> 5 -> 1 -> 2 -> 3.

Here is a breakdown of what happens:

Step 1: Remove the last 2 nodes (4 and 5).
Step 2: Attach them to the front of the list.
Step 3: The new head becomes node 4, and node 3 becomes the new tail pointing to null.

Edge Cases to Consider

The list is empty (head === null).
The list has only one node.
k is larger than the length of the list.
k is zero.
k is a multiple of the list length (resulting in the same list).

Why It Matters

The Rotate List problem is more than just an interview exercise. It tests several fundamental computer science concepts:

Linked list manipulation: Understanding how to traverse, count, and rewire pointers in a singly linked list.
Modular arithmetic: Handling cases where k exceeds the list length using the modulo operator.
Edge case reasoning: Writing robust code that does not break on degenerate inputs.
Algorithm optimization: Moving from a naive O(n*k) approach to an optimal O(n) solution.

Mastering this problem builds a strong foundation for more complex data structure challenges involving trees, graphs, and doubly linked lists.

Setting Up the Linked List Structure

Before solving the problem, we need a basic linked list node definition in JavaScript. We will use the ES6 class syntax for clarity.

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Helper function to build a linked list from an array
function buildList(arr) {
  if (arr.length === 0) return null;
  const head = new ListNode(arr[0]);
  let current = head;
  for (let i = 1; i < arr.length; i++) {
    current.next = new ListNode(arr[i]);
    current = current.next;
  }
  return head;
}

// Helper function to print a linked list
function printList(head) {
  const result = [];
  let current = head;
  while (current !== null) {
    result.push(current.val);
    current = current.next;
  }
  console.log(result.join(' -> '));
}

These helpers make it easier to test our solution with various inputs.

Approach 1: Naive Solution (Rotate One Step at a Time)

The most intuitive approach is to rotate the list one position at a time, repeating the process k times. Each rotation involves moving the last node to the front.

Implementation

function rotateRightNaive(head, k) {
  if (head === null || head.next === null || k === 0) {
    return head;
  }

  // First, find the length of the list
  let length = 1;
  let tail = head;
  while (tail.next !== null) {
    tail = tail.next;
    length++;
  }

  // Effective rotations needed
  k = k % length;
  if (k === 0) return head;

  for (let i = 0; i < k; i++) {
    // Find the new tail (second to last node)
    let newTail = head;
    while (newTail.next.next !== null) {
      newTail = newTail.next;
    }

    // The last node becomes the new head
    const newHead = newTail.next;
    newTail.next = null;
    newHead.next = head;
    head = newHead;
  }

  return head;
}

Complexity Analysis

Time Complexity: O(n * k) in the worst case, where n is the length of the list. This is inefficient when k is large.
Space Complexity: O(1), since we only use a few pointers.

While this approach works, it is not optimal for large inputs. Let us improve it.

Approach 2: Optimal Solution (Close the Loop)

The optimal approach takes advantage of the circular nature of the rotation. Instead of rotating one step at a time, we can:

Compute the length of the list.
Connect the tail to the head, forming a circular list.
Find the new tail, which is at position length - k.
Break the circle at the new tail to form the rotated list.

This reduces the time complexity to O(n) with a single pass after computing the length.

Step-by-Step Implementation

function rotateRight(head, k) {
  // Edge case: empty list or single node or no rotation
  if (head === null || head.next === null || k === 0) {
    return head;
  }

  // Step 1: Compute the length of the list and find the tail
  let length = 1;
  let tail = head;
  while (tail.next !== null) {
    tail = tail.next;
    length++;
  }

  // Step 2: Compute effective rotations
  k = k % length;
  if (k === 0) return head;

  // Step 3: Close the loop to form a circular list
  tail.next = head;

  // Step 4: Find the new tail at position (length - k)
  let stepsToNewTail = length - k;
  let newTail = head;
  for (let i = 1; i < stepsToNewTail; i++) {
    newTail = newTail.next;
  }

  // Step 5: The new head is the node after the new tail
  const newHead = newTail.next;

  // Step 6: Break the circle
  newTail.next = null;

  return newHead;
}

How It Works

Let us trace through the example 1 -> 2 -> 3 -> 4 -> 5 with k = 2:

The length is 5, and the tail is node 5.
Effective k = 2 % 5 = 2.
We connect node 5 to node 1, forming a circle.
The new tail is at position 5 - 2 = 3, which is node 3.
The new head is node 4.
We break the link from node 3 to node 4 by setting newTail.next = null.
The final list is 4 -> 5 -> 1 -> 2 -> 3.

Complexity Analysis

Time Complexity: O(n), where n is the length of the list. We traverse the list at most twice.
Space Complexity: O(1), as we only use a constant number of pointers.

Testing the Solution

Now let us test our optimal solution with several cases to ensure correctness.

// Test Case 1: Normal rotation
const list1 = buildList([1, 2, 3, 4, 5]);
const rotated1 = rotateRight(list1, 2);
printList(rotated1); // Output: 4 -> 5 -> 1 -> 2 -> 3

// Test Case 2: k is larger than the list length
const list2 = buildList([1, 2, 3]);
const rotated2 = rotateRight(list2, 5);
printList(rotated2); // Output: 2 -> 3 -> 1

// Test Case 3: k equals the list length
const list3 = buildList([1, 2, 3, 4]);
const rotated3 = rotateRight(list3, 4);
printList(rotated3); // Output: 1 -> 2 -> 3 -> 4

// Test Case 4: Empty list
const list4 = buildList([]);
const rotated4 = rotateRight(list4, 3);
printList(rotated4); // Output: (empty)

// Test Case 5: Single node
const list5 = buildList([42]);
const rotated5 = rotateRight(list5, 99);
printList(rotated5); // Output: 42

// Test Case 6: k is zero
const list6 = buildList([1, 2, 3]);
const rotated6 = rotateRight(list6, 0);
printList(rotated6); // Output: 1 -> 2 -> 3

All test cases should produce the expected outputs, confirming that our solution handles edge cases correctly.

Common Mistakes to Avoid

Forgetting the modulo operation: Without k = k % length, large values of k will cause unnecessary iterations or incorrect results.
Not handling the zero-rotation case: After applying the modulo, if k becomes 0, you should return the original head immediately to avoid breaking the list.
Off-by-one errors when finding the new tail: Remember that the new tail is at position length - k, and you need to traverse length - k - 1 steps from the head (or use a 1-based loop as shown above).
Forgetting to break the circular link: If you connect the tail to the head but forget to set newTail.next = null, you will end up with an infinite loop when traversing the result.
Ignoring null checks: Always check if the head is null or if the list has only one node before performing any operations.

Best Practices

1. Always Handle Edge Cases First

Start your function with guard clauses for empty lists, single-node lists, and zero rotations. This makes the code more readable and prevents unnecessary computation.

if (head === null || head.next === null || k === 0) {
  return head;
}

2. Use the Modulo Operator

The modulo operator is essential for handling cases where k is larger than the list length. It ensures you only perform the minimum necessary rotations.

k = k % length;
if (k === 0) return head;

3. Write Helper Functions for Testing

Functions like buildList and printList make it much easier to test and debug your solution. They also improve code readability.

4. Use Descriptive Variable Names

Instead of using generic names like node or ptr, use descriptive names such as tail, newTail, and newHead. This makes the logic self-documenting.

5. Test with Multiple Inputs

Always test your solution with a variety of inputs, including edge cases. This builds confidence that your code is robust and production-ready.

6. Avoid Mutating the Input Unnecessarily

In some scenarios, you may want to preserve the original list. If immutability is a requirement, consider creating a deep copy before performing the rotation.

Variations of the Problem

Once you understand the basic rotation, you can explore related challenges:

Rotate Left: Instead of moving the last k nodes to the front, move the first k nodes to the back. The logic is similar but the new tail is at position k.
Rotate a Doubly Linked List: The same principles apply, but you also need to update the prev pointers.
Rotate an Array: A similar problem that can be solved using reversal or cyclic replacements.
Rotate by Groups: Rotate nodes in groups of k, which is a more complex variation often seen in interviews.

Left Rotation Implementation

As a bonus, here is how you can implement a left rotation using the same circular list technique.

function rotateLeft(head, k) {
  if (head === null || head.next === null || k === 0) {
    return head;
  }

  // Compute length and find tail
  let length = 1;
  let tail = head;
  while (tail.next !== null) {
    tail = tail.next;
    length++;
  }

  k = k % length;
  if (k === 0) return head;

  // Close the loop
  tail.next = head;

  // For left rotation, the new tail is at position k
  let newTail = head;
  for (let i = 1; i < k; i++) {
    newTail = newTail.next;
  }

  const newHead = newTail.next;
  newTail.next = null;

  return newHead;
}

// Test: 1 -> 2 -> 3 -> 4 -> 5, k = 2
// Expected output: 3 -> 4 -> 5 -> 1 -> 2
const leftList = buildList([1, 2, 3, 4, 5]);
printList(rotateLeft(leftList, 2));

Conclusion

The Rotate List problem is an excellent exercise for strengthening your understanding of linked list manipulation and algorithmic thinking. By moving from a naive one-step-at-a-time approach to the optimal circular list technique, you learn how to identify inefficiencies and apply clever insights to reduce time complexity. Remember to always handle edge cases, use the modulo operator to normalize k, and test your solution thoroughly with diverse inputs. With these techniques in your toolkit, you will be well-prepared to tackle this problem and similar linked list challenges in both interviews and real-world development scenarios.