// ─────────────────────────────────────────────────────────────────────────────
// LINKED LISTS
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : pointer surgery; O(1) insert/delete given a node, O(n) access.
// TELL   : "ListNode", "in place", "O(1) extra space", "cycle", "middle", "nth from end", "reorder".
// SAY    : dummy / sentinel head, fast & slow pointers (Floyd's tortoise and hare), prev/cur/next,
//          two-pointer gap, splice, doubly linked list, head/tail sentinels.
// BIG-O  : O(n) time, O(1) space for almost everything here (recursion costs O(n) stack).
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

class ListNode {
  constructor(val = 0, next = null) { this.val = val; this.next = next; }
}
const fromArray = (arr) => arr.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (head) => { const out = []; for (let n = head; n; n = n.next) out.push(n.val); return out; };
assert.deepEqual(toArray(fromArray([1, 2, 3])), [1, 2, 3]);
assert.deepEqual(toArray(fromArray([])), []);

// ── 1. Reverse (iterative)  —  prev/cur; flip next pointer; return prev  —  O(n) / O(1)
function reverse(head) {
  let prev = null, cur = head;
  while (cur) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }
  return prev;
}
assert.deepEqual(toArray(reverse(fromArray([1, 2, 3, 4]))), [4, 3, 2, 1]);
assert.deepEqual(toArray(reverse(fromArray([1]))), [1]);
assert.equal(reverse(null), null);

// ── 2. Reverse (recursive)  —  reverse rest, then head.next.next = head  —  O(n) / O(n) stack
function reverseRec(head) {
  if (!head || !head.next) return head;
  const newHead = reverseRec(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}
assert.deepEqual(toArray(reverseRec(fromArray([1, 2, 3]))), [3, 2, 1]);
assert.equal(reverseRec(null), null);

// ── 3. Find middle (fast/slow)  —  fast moves 2, slow moves 1; slow = middle (second of two for even)  —  O(n) / O(1)
function middle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  return slow;
}
assert.equal(middle(fromArray([1, 2, 3, 4, 5])).val, 3);
assert.equal(middle(fromArray([1, 2, 3, 4])).val, 3); // for first-middle use: while (fast.next && fast.next.next)
assert.equal(middle(null), null);

// ── 4. Detect cycle + find cycle start (Floyd)  —  meet inside cycle; reset one to head; walk at same speed  —  O(n) / O(1)
function detectCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next; fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) { slow = slow.next; fast = fast.next; }
      return slow; // cycle entrance
    }
  }
  return null;
}
const cyc = fromArray([3, 2, 0, -4]);
cyc.next.next.next.next = cyc.next; // tail -> node(2)
assert.equal(detectCycle(cyc).val, 2);
assert.equal(detectCycle(fromArray([1, 2])), null);
assert.equal(detectCycle(null), null);

// ── 5. Merge two sorted lists  —  dummy head; attach smaller; append remainder  —  O(n+m) / O(1)
function mergeTwo(a, b) {
  const dummy = new ListNode();
  let t = dummy;
  while (a && b) {
    if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; }
    t = t.next;
  }
  t.next = a ?? b;
  return dummy.next;
}
assert.deepEqual(toArray(mergeTwo(fromArray([1, 2, 4]), fromArray([1, 3, 4]))), [1, 1, 2, 3, 4, 4]);
assert.deepEqual(toArray(mergeTwo(null, fromArray([0]))), [0]);
assert.deepEqual(toArray(mergeTwo(null, null)), []);

// ── 6. Remove nth from end  —  two pointers with gap n+1 from a dummy; when fast hits null, slow.next is the target  —  O(n) / O(1)
function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy, slow = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;
  while (fast) { fast = fast.next; slow = slow.next; }
  slow.next = slow.next.next;
  return dummy.next;
}
assert.deepEqual(toArray(removeNthFromEnd(fromArray([1, 2, 3, 4, 5]), 2)), [1, 2, 3, 5]);
assert.deepEqual(toArray(removeNthFromEnd(fromArray([1]), 1)), []);
assert.deepEqual(toArray(removeNthFromEnd(fromArray([1, 2]), 2)), [2]); // removing head

// ── 7. Reorder list (L0 Ln L1 Ln-1 ...)  —  middle, reverse second half, interleave  —  O(n) / O(1)
function reorderList(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }
  let second = reverse(slow.next);
  slow.next = null;
  let first = head;
  while (second) {
    const n1 = first.next, n2 = second.next;
    first.next = second; second.next = n1;
    first = n1; second = n2;
  }
  return head;
}
assert.deepEqual(toArray(reorderList(fromArray([1, 2, 3, 4, 5]))), [1, 5, 2, 4, 3]);
assert.deepEqual(toArray(reorderList(fromArray([1, 2, 3, 4]))), [1, 4, 2, 3]);
assert.deepEqual(toArray(reorderList(fromArray([1]))), [1]);

// ── 8. Palindrome linked list  —  middle, reverse second half, compare  —  O(n) / O(1)
function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let second = reverse(slow), first = head;
  while (second) { if (first.val !== second.val) return false; first = first.next; second = second.next; }
  return true;
}
assert.equal(isPalindrome(fromArray([1, 2, 2, 1])), true);
assert.equal(isPalindrome(fromArray([1, 2])), false);
assert.equal(isPalindrome(fromArray([7])), true);

// ── 9. Add two numbers (digits reversed)  —  carry; loop while either list or carry  —  O(max(n,m)) / O(1) extra
function addTwoNumbers(a, b) {
  const dummy = new ListNode();
  let t = dummy, carry = 0;
  while (a || b || carry) {
    const sum = (a?.val ?? 0) + (b?.val ?? 0) + carry;
    carry = (sum / 10) | 0;
    t = t.next = new ListNode(sum % 10);
    a = a?.next ?? null; b = b?.next ?? null;
  }
  return dummy.next;
}
assert.deepEqual(toArray(addTwoNumbers(fromArray([2, 4, 3]), fromArray([5, 6, 4]))), [7, 0, 8]); // 342 + 465 = 807
assert.deepEqual(toArray(addTwoNumbers(fromArray([9, 9]), fromArray([1]))), [0, 0, 1]); // carry out
assert.deepEqual(toArray(addTwoNumbers(fromArray([0]), fromArray([0]))), [0]);

// ── 10. Intersection of two lists  —  two pointers; on null, switch to the other head; meet after a+b steps  —  O(n+m) / O(1)
function getIntersection(a, b) {
  let p = a, q = b;
  while (p !== q) { p = p ? p.next : b; q = q ? q.next : a; }
  return p;
}
const shared = fromArray([8, 4, 5]);
const la = new ListNode(4, new ListNode(1, shared)), lb = new ListNode(5, new ListNode(6, new ListNode(1, shared)));
assert.equal(getIntersection(la, lb), shared);
assert.equal(getIntersection(fromArray([1]), fromArray([2])), null);

// ── 11. Remove duplicates from sorted list  —  skip while cur.val === cur.next.val  —  O(n) / O(1)
function deleteDuplicates(head) {
  for (let cur = head; cur && cur.next;) {
    if (cur.val === cur.next.val) cur.next = cur.next.next; else cur = cur.next;
  }
  return head;
}
assert.deepEqual(toArray(deleteDuplicates(fromArray([1, 1, 2, 3, 3]))), [1, 2, 3]);
assert.deepEqual(toArray(deleteDuplicates(fromArray([1, 1, 1]))), [1]);
assert.deepEqual(toArray(deleteDuplicates(null)), []);

// ── 12. Doubly linked list sketch + LRU structure  —  head/tail sentinels; O(1) remove(node) and addFront(node); Map key -> node
class DNode { constructor(key, val) { this.key = key; this.val = val; this.prev = null; this.next = null; } }
class LRU {
  #cap; #map = new Map(); #head = new DNode(); #tail = new DNode(); // sentinels
  constructor(cap) { this.#cap = cap; this.#head.next = this.#tail; this.#tail.prev = this.#head; }
  #remove(n) { n.prev.next = n.next; n.next.prev = n.prev; }
  #addFront(n) { n.next = this.#head.next; n.prev = this.#head; this.#head.next.prev = n; this.#head.next = n; }
  get(k) { const n = this.#map.get(k); if (!n) return -1; this.#remove(n); this.#addFront(n); return n.val; }
  put(k, v) {
    if (this.#map.has(k)) { this.#remove(this.#map.get(k)); }
    const n = new DNode(k, v); this.#map.set(k, n); this.#addFront(n);
    if (this.#map.size > this.#cap) { const lru = this.#tail.prev; this.#remove(lru); this.#map.delete(lru.key); }
  }
}
const lru = new LRU(2);
lru.put(1, 1); lru.put(2, 2); lru.get(1); lru.put(3, 3);
assert.deepEqual([lru.get(2), lru.get(1), lru.get(3)], [-1, 1, 3]);

// ── 13. Reverse in k-groups  —  check k nodes exist; reverse that segment; link prev-group tail to new head  —  O(n) / O(1)
function reverseKGroup(head, k) {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;
  for (;;) {
    let kth = groupPrev;
    for (let i = 0; i < k && kth; i++) kth = kth.next;
    if (!kth) return dummy.next; // fewer than k left: leave as is
    const groupNext = kth.next;
    let prev = groupNext, cur = groupPrev.next; // reverse [groupPrev.next .. kth], tail points to groupNext
    while (cur !== groupNext) { const nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }
    const oldHead = groupPrev.next;
    groupPrev.next = kth;
    groupPrev = oldHead;
  }
}
assert.deepEqual(toArray(reverseKGroup(fromArray([1, 2, 3, 4, 5]), 2)), [2, 1, 4, 3, 5]);
assert.deepEqual(toArray(reverseKGroup(fromArray([1, 2, 3, 4, 5]), 3)), [3, 2, 1, 4, 5]);
assert.deepEqual(toArray(reverseKGroup(fromArray([1]), 1)), [1]);

console.log('ok: algorithms/linked-lists.js');