Linked lists — across Python, Go, TypeScript & C++

Pointer rewiring patterns: save the next node before changing links, use a dummy for head edits, and guard nil/null before two-step hops. Traversal is O(n); rewiring at known nodes is O(1).

Node definitions

PythonGoTypeScriptC++
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next		 type ListNode struct {
    Val int
    Next *ListNode
}		 class ListNode {
  constructor(public val = 0,
    public next: ListNode | null = null) {}
}		 struct ListNode {
  int val;
  ListNode* next;
  ListNode(int v=0, ListNode* n=nullptr) : val(v), next(n) {}
};

Reverse — prev / curr / next

PythonGoTypeScriptC++
O(n) time, O(1) space.
def reverse(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev		 O(n), O(1).
var prev *ListNode
curr := head
for curr != nil {
  next := curr.Next
  curr.Next = prev
  prev, curr = curr, next
}
return prev		 O(n), O(1).
let prev: ListNode | null = null
let curr = head
while (curr) {
  const next = curr.next
  curr.next = prev
  prev = curr
  curr = next
}
return prev		 O(n), O(1).
ListNode *prev=nullptr, *curr=head;
while (curr) {
  ListNode* next = curr->next;
  curr->next = prev;
  prev = curr;
  curr = next;
}
return prev;

Merge two sorted lists — dummy node

PythonGoTypeScriptC++
O(a+b) time, O(1) space.
def merge(a, b):
    dummy = ListNode()
    tail = dummy
    while a and 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 or b
    return dummy.next		 O(a+b), O(1).
dummy := &ListNode{}
tail := dummy
for a != nil && b != nil {
  if a.Val <= b.Val { tail.Next, a = a, a.Next } else { tail.Next, b = b, b.Next }
  tail = tail.Next
}
if a != nil { tail.Next = a } else { tail.Next = b }
return dummy.Next		 O(a+b), O(1).
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
return dummy.next		 O(a+b), O(1).
ListNode dummy;
ListNode* 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 ? a : b;
return dummy.next;

Fast / slow — middle and cycle

PythonGoTypeScriptC++
Middle: O(n), O(1).
def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow		 Middle: O(n), O(1).
slow, fast := head, head
for fast != nil && fast.Next != nil {
  slow = slow.Next
  fast = fast.Next.Next
}
return slow		 Middle: O(n), O(1).
let slow = head, fast = head
while (fast && fast.next) {
  slow = slow!.next
  fast = fast.next.next
}
return slow		 Middle: O(n), O(1).
auto slow = head;
auto fast = head;
while (fast && fast->next) {
  slow = slow->next;
  fast = fast->next->next;
}
return slow;
Cycle: O(n), O(1).
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False		 Cycle: O(n), O(1).
slow, fast := head, head
for fast != nil && fast.Next != nil {
  slow = slow.Next
  fast = fast.Next.Next
  if slow == fast { return true }
}
return false		 Cycle: O(n), O(1).
let slow = head, fast = head
while (fast && fast.next) {
  slow = slow!.next
  fast = fast.next.next
  if (slow === fast) return true
}
return false		 Cycle: O(n), O(1).
auto slow = head;
auto fast = head;
while (fast && fast->next) {
  slow = slow->next;
  fast = fast->next->next;
  if (slow == fast) return true;
}
return false;

Delete nth from end — gap by n

PythonGoTypeScriptC++
O(n) time, O(1) space; assume valid n.
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n):
        fast = fast.next
    while fast.next:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next		 O(n), O(1).
dummy := &ListNode{Next: head}
fast, slow := dummy, dummy
for i := 0; i < n; i++ { fast = fast.Next }
for fast.Next != nil { fast = fast.Next; slow = slow.Next }
slow.Next = slow.Next.Next
return dummy.Next		 O(n), O(1).
const dummy = new ListNode(0, head)
let fast = dummy, slow = dummy
for (let i = 0; i < n; i++) fast = fast.next!
while (fast.next) { fast = fast.next; slow = slow.next! }
slow.next = slow.next!.next
return dummy.next		 O(n), O(1).
ListNode dummy(0, head);
auto fast = &dummy;
auto slow = &dummy;
for (int i=0; i<n; ++i) fast = fast->next;
while (fast->next) { fast = fast->next; slow = slow->next; }
auto victim = slow->next;
slow->next = victim->next;
delete victim;
return dummy.next;

Splice — move a known segment

PythonGoTypeScriptC++
O(1) after locating pointers; dst is outside the segment.
def splice_after(before, last, dst):
    first = before.next
    after = last.next
    before.next = after
    last.next = dst.next
    dst.next = first		 O(1) after search; dst outside.
first := before.Next
after := last.Next
before.Next = after
last.Next = dst.Next
dst.Next = first		 O(1) after search; dst outside.
const first = before.next!
const after = last.next
before.next = after
last.next = dst.next
dst.next = first		 O(1) after search; dst outside.
auto first = before->next;
auto after = last->next;
before->next = after;
last->next = dst->next;
dst->next = first;

Gotchas

PythonGoTypeScriptC++
  • Save nxt = curr.next before curr.next = prev; otherwise the rest of the list is gone.
  • Use a dummy for merge/delete/splice when the head might change.
  • A node is truthy by default; test identity with is for cycle detection.
  • var p *ListNode is nil; p.Next = x panics. Create a dummy with &ListNode{}.
  • A nil pointer receiver method can be called, but it still panics when the method reads p.Next.
  • Always guard two-step hops as fast != nil && fast.Next != nil.
  • interface Node collides with the DOM type; name list nodes ListNode.
  • fast?.next?.next may become undefined; keep node links consistently null.
  • Do not use optional chaining on the left side of rewiring; slow?.next = x is invalid.
  • delete victim only when this function owns heap nodes; never delete stack or borrowed nodes.
  • After delete, the pointer is dangling; do not read victim->next.
  • Guard pointer hops as fast && fast->next, then move fast->next->next.

Docs: docs.python.org · pkg.go.dev · developer.mozilla.org · en.cppreference.com