In-place Linked List Manipulation

// Template 1: reverse a list in place. prev heads the part that is already reversed; curr is the next node to flip.
// Save curr.next BEFORE overwriting it, or the rest of the list is lost.
export function reverseList(head) {
  let prev = null;
  let curr = head;
  while (curr) {
    const next = curr.next; // 1. save the rest
    curr.next = prev;       // 2. flip the arrow
    prev = curr;            // 3. move both pointers forward
    curr = next;
  }
  return prev;              // the old tail is the new head
}

import { ListNode } from './list.js';

// Template 2: a dummy node in front of the head, so the head can be removed or replaced like any other node.
export function removeAll(head, value) {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next) {
    if (prev.next.val === value) prev.next = prev.next.next; // unlink; don't move: the new prev.next is unchecked
    else prev = prev.next;
  }
  return dummy.next; // may not be the old head any more
}

// Building a list: with a dummy and a tail pointer, appending never needs a special case for the first node.
export function mergeSorted(a, b) {
  const dummy = new ListNode();
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }
  tail.next = a ?? b; // the rest of the other list is already sorted
  return dummy.next;
}

import { ListNode } from './list.js';

// Template 3: reverse the k nodes after `before` (they must exist) and splice them back into place.
// Returns the segment's new last node, which is the `before` of whatever comes next.
export function reverseAfter(before, k) {
  const first = before.next; // will become the segment's last node
  let prev = null;
  let curr = first;
  for (let i = 0; i < k; i++) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  before.next = prev; // before → the segment's new first node
  first.next = curr;  // the segment's new last node → the rest of the list
  return first;
}

// Example: swap every two adjacent nodes, which is "reverse in groups of 2".
export function swapPairs(head) {
  const dummy = new ListNode(0, head);
  let before = dummy;
  while (before.next && before.next.next) before = reverseAfter(before, 2);
  return dummy.next;
}

import { reverseList } from './reverse.js';

// Template 4: interleave two lists in place, a1 → b1 → a2 → b2 → …
// Save BOTH successors before rewiring; whichever list is longer keeps its leftover nodes at the end.
export function weave(a, b) {
  const head = a;
  while (a && b) {
    const aNext = a.next;
    const bNext = b.next;
    a.next = b;
    b.next = aNext ?? bNext; // if a has run out, b keeps the rest of its own list
    a = aNext;
    b = bNext;
  }
  return head;
}

// The combo: L0 → Ln → L1 → Ln-1 → … in place. Find the middle, cut, reverse the back half, weave.
export function fold(head) {
  if (!head) return head;
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) { // slow ends on the last node of the front half
    slow = slow.next;
    fast = fast.next.next;
  }
  const back = reverseList(slow.next);
  slow.next = null; // cut, or the front half still runs into the back half
  return weave(head, back);
}