Skip to main content
Mapagam

Reversing LinkedList Nodes In-Place

1. Understanding In-Place Reversal Technique

The in-place reversal of a linked list is a fundamental algorithm pattern used to reverse the direction of links in a singly linked list without using extra space for another data structure.

Concept Description Use Case
Pointer Manipulation Reversing a linked list involves changing the direction of pointers from next to point to the previous node instead of the next node. Efficiently reversing a list in memory-constrained environments
Three-Pointer Technique Uses three pointers: previous, current, and next to keep track of nodes during reversal. Standard approach for reversing singly linked lists

Example: Reversing a LinkedList In-Place

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

function reverseLinkedList(head) {
  let previous = null;
  let current = head;

  while (current !== null) {
    const next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }

  return previous;
}

// Example usage:
const node3 = new ListNode(3);
const node2 = new ListNode(2, node3);
const node1 = new ListNode(1, node2);

const reversedHead = reverseLinkedList(node1);
Note: The function returns the new head of the reversed list, which was originally the last node.

2. Reversing Entire LinkedList

Property Description Example
head Pointer to the first node in the list Node head = new Node(1);
next Pointer to the next node in the list current.next = previous;

Example: Reversing a LinkedList In-Place

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

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode current = head;

    while (current != null) {
        ListNode nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }

    return prev;
}
Note: The algorithm uses three pointers to reverse the links in-place, maintaining O(1) space complexity.

3. Reversing LinkedList Sublist

Property Description Usage
head Pointer to the first node in the list Start of the reversal process
start Index of the first node in sublist to reverse Determines where reversal begins
end Index of the last node in sublist to reverse Determines where reversal ends

Example: Reversing a Sublist

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

function reverseSublist(head, start, end) {
  if (!head || start === end) return head;

  let dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  for (let i = 0; i < start; i++) {
    prev = prev.next;
  }

  let current = prev.next;
  for (let i = start; i < end; i++) {
    let nextNode = current.next;
    current.next = nextNode.next;
    nextNode.next = prev.next;
    prev.next = nextNode;
  }

  return dummy.next;
}

// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const result = reverseSublist(list, 1, 3);
// Result: [1, 4, 3, 2, 5]
Note: The indices are 0-based. Reversing from index 1 to 3 means reversing nodes at positions 1, 2, and 3.

4. Reversing K-Group Nodes

Property Description Example
k Number of nodes to reverse in each group 3
head Head of the linked list [1,2,3,4,5]

Example: Reversing K-Group Nodes

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

function reverseKGroup(head, k) {
  const dummy = new ListNode(0);
  dummy.next = head;
  let prevGroupEnd = dummy;

  while (true) {
    let groupStart = prevGroupEnd.next;
    let groupEnd = groupStart;

    for (let i = 0; i < k - 1; i++) {
      if (!groupEnd) return dummy.next;
      groupEnd = groupEnd.next;
    }

    if (!groupEnd) return dummy.next;

    const nextGroupStart = groupEnd.next;
    let prev = null;
    let current = groupStart;

    while (current !== nextGroupStart) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    groupStart.next = nextGroupStart;
    prevGroupEnd.next = groupEnd;
    prevGroupEnd = groupStart;
  }
}

// Example usage:
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const result = reverseKGroup(head, 2);
// Result: [2,1,4,3,5]
Note: If the number of nodes is not a multiple of k, the remaining nodes at the end should remain as they are.

5. Reversing Alternating K-Groups

Reversing alternating k-groups involves reversing nodes in groups of size k, but only reversing every other group (i.e., reverse 1st group, skip 2nd, reverse 3rd, and so on).

Group Nodes in Group Action Result After Reversal
Group 1 1 → 2 → 3 → 4 Reverse 4 → 3 → 2 → 1
Group 2 5 → 6 → 7 → 8 Skip 5 → 6 → 7 → 8
Group 3 9 → 10 → 11 → 12 Reverse 12 → 11 → 10 → 9

Example: Reversing Alternating K-Groups

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

function reverseAlternatingKGroups(head, k) {
  if (!head || k <= 1) return head;

  let dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  let count = 0;
  let current = head;

  while (current) {
    count++;
    if (count % (2 * k) === 1) {
      // Reverse the first k nodes in this group
      let tail = reverseKNodes(current, k);
      prev.next = tail;
      current = tail;
    } else if (count % (2 * k) === 0) {
      // Skip the second k nodes in this group
      let temp = current;
      for (let i = 0; i < k; i++) {
        if (!temp) break;
        temp = temp.next;
      }
      prev.next = current;
      current = temp;
    } else {
      // Move to next node
      prev = current;
      current = current.next;
    }
  }

  return dummy.next;
}

function reverseKNodes(head, k) {
  let prev = null;
  let current = head;

  for (let i = 0; i < k; i++) {
    let next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  head.next = current; // Connect the remaining list
  return prev; // New head of reversed group
}
Note: This approach reverses every other k-group in the list, skipping the second group in each pair.

6. Rotating LinkedList by K Positions

Property Description Example
k Number of positions to rotate the list 2
head Pointer to the first node in the list 1 -> 2 -> 3 -> 4 -> 5

Example: Rotating a LinkedList by K=2

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

function rotateRight(head, k) {
  if (!head || !head.next || k === 0) return head;

  let tail = head;
  let len = 1;
  while (tail.next) {
    tail = tail.next;
    len++;
  }

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

  tail.next = head; // Make it circular
  let newTail = head;
  for (let i = 0; i < len - k - 1; i++) {
    newTail = newTail.next;
  }

  let newHead = newTail.next;
  newTail.next = null;

  return newHead;
}

// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
const rotated = rotateRight(list, 2);
// Result: 4 -> 5 -> 1 -> 2 -> 3
Note: The rotation is done in-place, modifying the links between nodes without using extra space for another list.

7. Swapping Nodes in Pairs

Property Description Example
Algorithm Swap adjacent nodes in pairs without modifying node values 1 -> 2 -> 3 -> 4 => 2 -> 1 -> 4 -> 3
Time Complexity O(n) - Traverse list once
Space Complexity O(1) - Only use a few pointers

Example: Swapping Nodes in Pairs

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

function swapPairs(head) {
  const dummy = new ListNode(0);
  dummy.next = head;
  let prev = dummy;

  while (prev.next && prev.next.next) {
    const first = prev.next;
    const second = prev.next.next;

    // Swapping
    first.next = second.next;
    second.next = first;
    prev.next = second;

    // Move pointer forward
    prev = first;
  }

  return dummy.next;
}

// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
const swapped = swapPairs(list);
// Result: 2 -> 1 -> 4 -> 3
Note: The dummy node simplifies edge cases like an empty list or a single-node list.

8. Reversing Every K Elements

Property Description Example
k Number of nodes to reverse in each group k = 3
head Head of the linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

Example: Reverse Every K Nodes

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

function reverseKGroup(head, k) {
  const dummy = new ListNode(0);
  dummy.next = head;
  let prevGroupEnd = dummy;

  while (true) {
    let groupStart = prevGroupEnd.next;
    let groupEnd = groupStart;

    // Find the end of the current group
    for (let i = 0; i < k - 1 && groupEnd !== null; i++) {
      groupEnd = groupEnd.next;
    }

    if (groupEnd === null) break;

    const nextGroupStart = groupEnd.next;

    // Reverse the current group
    let prev = null;
    let current = groupStart;

    while (current !== nextGroupStart) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    // Reconnect the reversed group
    prevGroupEnd.next = groupEnd;
    groupStart.next = nextGroupStart;
    prevGroupEnd = groupStart;
  }

  return dummy.next;
}

// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6))))));
const result = reverseKGroup(list, 2);
// Result: 2 -> 1 -> 4 -> 3 -> 6 -> 5
Note: If the number of nodes is not a multiple of k, the remaining nodes at the end are left as they are.

9. Reordering LinkedList

Operation Description Time Complexity Space Complexity
Reorder List Reorders a singly linked list such that nodes are arranged in the pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... O(n) O(1)

Example: Reordering a LinkedList

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

function reorderList(head) {
  if (!head || !head.next) return;

  // Step 1: Find the middle of the list
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Step 2: Reverse the second half
  let prev = null;
  let curr = slow.next;
  slow.next = null; // Break the list

  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Step 3: Merge the two halves
  let firstHalf = head;
  let secondHalf = prev;

  while (secondHalf) {
    let next1 = firstHalf.next;
    let next2 = secondHalf.next;

    firstHalf.next = secondHalf;
    secondHalf.next = next1;

    firstHalf = next1;
    secondHalf = next2;
  }
}

// Example usage:
const list = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
reorderList(list);
// Result: 1 → 4 → 2 → 3

10. Reversing LinkedList Second Half

Step Description Action Code
1 Find the middle of the list using slow and fast pointers Use two pointers: slow moves one step, fast moves two steps 
let slow = head;
let fast = head;
while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
}
2 Reverse the second half starting from slow Reverse the linked list from slow to end 
function reverseLinkedList(head) {
    let prev = null;
    let current = head;
    while (current) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }
    return prev;
}
let secondHalf = reverseLinkedList(slow);
3 Reconnect the first half to the reversed second half Adjust pointers so that the first half connects to the reversed second half 
let firstHalf = head;
let secondHalfReversed = secondHalf;

// Connect the first half to the reversed second half
while (secondHalfReversed) {
    let temp = firstHalf.next;
    firstHalf.next = secondHalfReversed;
    secondHalfReversed = secondHalfReversed.next;
    firstHalf.next.next = temp;
    firstHalf = temp;
}

Example: Reversing Second Half of LinkedList

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

function reverseSecondHalf(head) {
    if (!head || !head.next) return head;

    let slow = head;
    let fast = head;

    // Step 1: Find the middle
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // Step 2: Reverse the second half
    let prev = null;
    let current = slow;
    while (current) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    // Step 3: Reconnect the halves
    let firstHalf = head;
    let secondHalfReversed = prev;

    while (secondHalfReversed) {
        let temp = firstHalf.next;
        firstHalf.next = secondHalfReversed;
        secondHalfReversed = secondHalfReversed.next;
        firstHalf.next.next = temp;
        firstHalf = temp;
    }

    return head;
}

// Example usage:
let node1 = new ListNode(1);
let node2 = new ListNode(2);
let node3 = new ListNode(3);
let node4 = new ListNode(4);
let node5 = new ListNode(5);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;

let result = reverseSecondHalf(node1);
// Result: [1, 4, 2, 3, 5]

Was this article helpful?

Related Cheat Sheets