Linked Lists

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

// Built by hand, so the shape is obvious: 1 → 2 → 3 → null
const third = new ListNode(3);
const second = new ListNode(2, third);
const head = new ListNode(1, second);

let node = head;
while (node !== null) {
  console.log('value:', node.val, '| has next:', node.next !== null);
  node = node.next;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class ListNode {
  constructor(val, next = null) { this.val = val; this.next = next; }
}

function toList(values) {
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
  return head;
}

function toArray(head) {
  const out = [];
  for (let n = head; n !== null; n = n.next) out.push(n.val);
  return out;
}

const list = toList([1, 2, 3, 4, 5]);
console.log('built:', toArray(list));
console.log('length:', toArray(list).length);
console.log('empty list:', toArray(toList([])));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => { const o = []; for (let n = h; n; n = n.next) o.push(n.val); return o; };

// Without a dummy: the head needs its own branch, which is easy to get wrong.
function removeAllAwkward(head, target) {
  while (head !== null && head.val === target) head = head.next;   // special case
  let node = head;
  while (node !== null && node.next !== null) {
    if (node.next.val === target) node.next = node.next.next;
    else node = node.next;
  }
  return head;
}

// With a dummy: one uniform loop, no special case.
function removeAll(head, target) {
  const dummy = new ListNode(0, head);
  let node = dummy;
  while (node.next !== null) {
    if (node.next.val === target) node.next = node.next.next;   // skip it
    else node = node.next;
  }
  return dummy.next;
}

console.log('awkward:', toArray(removeAllAwkward(toList([7, 7, 1, 2, 7, 3]), 7)));
console.log('dummy:  ', toArray(removeAll(toList([7, 7, 1, 2, 7, 3]), 7)));
console.log('all removed:', toArray(removeAll(toList([7, 7, 7]), 7)));
console.log('empty:  ', toArray(removeAll(toList([]), 7)));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => { const o = []; for (let n = h; n; n = n.next) o.push(n.val); return o; };

function reverseList(head) {
  let prev = null;
  let node = head;
  while (node !== null) {
    const next = node.next;   // 1. remember the rest BEFORE we overwrite it
    node.next = prev;         // 2. flip this node's arrow backwards
    prev = node;              // 3. prev moves up
    node = next;              // 4. and so do we
  }
  return prev;                // node is null; prev is the new head
}

// Trace it so the four lines stop being magic.
function reverseTraced(head) {
  let prev = null, node = head, step = 0;
  while (node !== null) {
    console.log(`step ${step++}: at ${node.val} | reversed so far: [${toArray(prev)}] | remaining: [${toArray(node)}]`);
    const next = node.next;
    node.next = prev;
    prev = node;
    node = next;
  }
  return prev;
}

console.log('result:', toArray(reverseList(toList([1, 2, 3, 4, 5]))));
console.log('single:', toArray(reverseList(toList([1]))));
console.log('empty: ', toArray(reverseList(toList([]))));
console.log('--- traced ---');
reverseTraced(toList([1, 2, 3]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => { const o = []; for (let n = h; n; n = n.next) o.push(n.val); return o; };

function reverseRecursive(head) {
  if (head === null || head.next === null) return head;   // base: 0 or 1 node
  const newHead = reverseRecursive(head.next);            // reverse the rest
  head.next.next = head;                                  // the node after me points back at me
  head.next = null;                                       // and I become the tail
  return newHead;
}

console.log(toArray(reverseRecursive(toList([1, 2, 3, 4]))));
// O(n) time but O(n) SPACE, because of the call stack. The iterative
// version is O(1) space, which is why interviewers prefer it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);

function middleNode(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

console.log('[1,2,3,4,5] middle:', middleNode(toList([1, 2, 3, 4, 5])).val);      // 3
console.log('[1,2,3,4] middle:  ', middleNode(toList([1, 2, 3, 4])).val);         // 3, the second of the two
console.log('[1] middle:        ', middleNode(toList([1])).val);                   // 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;    // compare NODES, not values
  }
  return false;
}

// Where does the cycle begin? After they meet, reset one pointer to the head
// and advance both one step at a time; they meet at the entry point.
function cycleStart(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let a = head;
      while (a !== slow) { a = a.next; slow = slow.next; }
      return a;
    }
  }
  return null;
}

// Build 1 → 2 → 3 → 4 → back to 2
const n1 = new ListNode(1), n2 = new ListNode(2), n3 = new ListNode(3), n4 = new ListNode(4);
n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n2;

console.log('cyclic list has a cycle:', hasCycle(n1));
console.log('cycle starts at value:', cycleStart(n1).val);

const clean = new ListNode(1, new ListNode(2, new ListNode(3)));
console.log('clean list has a cycle:', hasCycle(clean), '| start:', cycleStart(clean));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => { const o = []; for (let n = h; n; n = n.next) o.push(n.val); return o; };

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let lead = dummy, trail = dummy;

  for (let i = 0; i < n; i++) lead = lead.next;   // open a gap of n
  while (lead.next !== null) {                     // slide both to the end
    lead = lead.next;
    trail = trail.next;
  }
  trail.next = trail.next.next;                    // trail is just before the target
  return dummy.next;
}

console.log(toArray(removeNthFromEnd(toList([1, 2, 3, 4, 5]), 2)));   // [1,2,3,5]
console.log(toArray(removeNthFromEnd(toList([1]), 1)));               // []
console.log(toArray(removeNthFromEnd(toList([1, 2]), 1)));            // [1]
console.log(toArray(removeNthFromEnd(toList([1, 2]), 2)));            // [2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => { const o = []; for (let n = h; n; n = n.next) o.push(n.val); return o; };

function mergeTwoLists(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;

  while (a !== null && b !== null) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a !== null ? a : b;   // attach whatever is left, no loop needed
  return dummy.next;
}

console.log(toArray(mergeTwoLists(toList([1, 3, 5]), toList([2, 4, 6]))));
console.log(toArray(mergeTwoLists(toList([]), toList([0]))));
console.log(toArray(mergeTwoLists(toList([1, 1]), toList([1]))));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class ListNode { constructor(val, next = null) { this.val = val; this.next = next; } }
const toList = (a) => a.reduceRight((next, val) => new ListNode(val, next), null);
const toArray = (h) => { const o = []; for (let n = h; n; n = n.next) o.push(n.val); return o; };

// L0 → Ln → L1 → Ln-1 → ... Three well-known steps, each already covered above.
function reorderList(head) {
  if (head === null || head.next === null) return head;

  // 1. Find the FIRST middle and cut the list in two.
  let slow = head, fast = head;
  while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; }
  let second = slow.next;
  slow.next = null;

  // 2. Reverse the second half.
  let prev = null;
  while (second !== null) { const nx = second.next; second.next = prev; prev = second; second = nx; }

  // 3. Weave the two halves together.
  let a = head, b = prev;
  while (b !== null) {
    const an = a.next, bn = b.next;
    a.next = b;
    if (an === null) break;
    b.next = an;
    a = an; b = bn;
  }
  return head;
}

console.log(toArray(reorderList(toList([1, 2, 3, 4]))));        // [1,4,2,3]
console.log(toArray(reorderList(toList([1, 2, 3, 4, 5]))));     // [1,5,2,4,3]
console.log(toArray(reorderList(toList([1, 2]))));              // [1,2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52class DNode {
  constructor(val) { this.val = val; this.prev = null; this.next = null; }
}

class DList {
  #head = new DNode(null);   // sentinels: never removed, so no null checks
  #tail = new DNode(null);
  #size = 0;

  constructor() { this.#head.next = this.#tail; this.#tail.prev = this.#head; }

  get size() { return this.#size; }

  /* O(1): insert just after the head sentinel. */
  addFirst(val) {
    const node = new DNode(val);
    node.next = this.#head.next;
    node.prev = this.#head;
    this.#head.next.prev = node;
    this.#head.next = node;
    this.#size++;
    return node;
  }

  /* O(1): unlink a node you already hold. No search needed. */
  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    this.#size--;
    return node.val;
  }

  removeLast() {
    if (this.#size === 0) return null;
    return this.remove(this.#tail.prev);
  }

  toArray() {
    const out = [];
    for (let n = this.#head.next; n !== this.#tail; n = n.next) out.push(n.val);
    return out;
  }
}

const d = new DList();
d.addFirst('c'); d.addFirst('b');
const nodeA = d.addFirst('a');
console.log('list:', d.toArray(), '| size:', d.size);

d.remove(nodeA);                       // O(1), we held the node
console.log('after removing a:', d.toArray());
console.log('removeLast returned:', d.removeLast(), '→', d.toArray());