Linked List In-Place Reversal

A linked list is a fundamental data structure where elements (nodes) are linked together using pointers. Reversing a linked list is a common operation, and doing it in-place means reversing the links without using additional memory (i.e., no auxiliary data structures).

In this article, we will explore the in-place reversal technique with examples in JavaScript.

Why Reverse a Linked List?

Reversing a linked list is a crucial technique in various problems, such as:

• Reversing sublists within a linked list (e.g., reversing nodes in k-groups)
• Checking for palindrome linked lists
• Rearranging linked lists for specific orderings
• Implementing efficient stack operations

Approach to In-Place Reversal

The key idea in in-place reversal is to modify the next pointers of the nodes so that they point backward instead of forward. This is done by maintaining three pointers:

1. Previous (prev): Tracks the node before the current one
2. Current (curr): Tracks the node currently being processed
3. Next (nextTemp): Stores the next node to prevent losing the reference

Algorithm Steps:

1. Initialize prev as null and curr as the head of the list.

2. Iterate through the list:

   • Store curr.next in nextTemp.
   • Reverse the link (curr.next = prev).

3. Move prev and curr forward.

When curr becomes null, prev will be the new head of the reversed list.

JavaScript Implementation

Below is an implementation of in-place reversal of a singly linked list:

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

function reverseLinkedList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    let nextTemp = curr.next; // Store next node
    curr.next = prev; // Reverse the link
    prev = curr; // Move prev forward
    curr = nextTemp; // Move curr forward
  }

  return prev; // New head
}

// Example usage:
function printList(head) {
  let curr = head;
  let output = [];
  while (curr) {
    output.push(curr.value);
    curr = curr.next;
  }
  console.log(output.join(" -> "));
}

// Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

console.log("Original List:");
printList(head);

head = reverseLinkedList(head);

console.log("Reversed List:");
printList(head);

Time and Space Complexity

Time Complexity: (Each node is visited once)

Space Complexity: (No extra memory used apart from a few pointers)

Variations of In-Place Reversal

Reverse a sublist (from position m to n)

In some cases, you may need to reverse only a portion of the linked list instead of the entire list.

function reverseBetween(head, m, n) {
  if (!head) return null;
  let dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  for (let i = 0; i < m - 1; i++) {
    prev = prev.next;
  }

  let curr = prev.next;
  let next = null;
  for (let i = 0; i < n - m; i++) {
    next = curr.next;
    curr.next = next.next;
    next.next = prev.next;
    prev.next = next;
  }

  return dummy.next;
}

// Example usage
// head: 5 -> 4 -> 3 -> 2 -> 1
console.log("Reversing sublist from position 2 to 4:");
printList(reverseBetween(head, 2, 4)); // 5 -> 2 -> 3 -> 4 -> 1

Reverse linked list in k-group segments

Instead of reversing the entire list, sometimes you need to reverse it in groups of k elements.

function reverseKGroup(head, k) {
  let count = 0;
  let curr = head;
  while (curr && count < k) {
    curr = curr.next;
    count++;
  }

  if (count === k) {
    curr = reverseKGroup(curr, k);
    while (count-- > 0) {
      let temp = head.next;
      head.next = curr;
      curr = head;
      head = temp;
    }
    head = curr;
  }
  return head;
}

// Example usage
// head: 5 -> 2 -> 3 -> 4 -> 1
console.log("Reversing list in k-group segments (k=3):");
printList(reverseKGroup(head, 3)); // 3 -> 2 -> 5 -> 4 -> 1