🔧 PHP Linked List Operations

Pattern 1 — Reverse a Linked List

🧠 How to Approach This

Step 1 — Recognize the pattern: In-place pointer reversal.

Step 2 — Brute force (what NOT to do): Push to stack, rebuild — O(n) space.

Step 3 — Optimal insight: Track prev, curr, next — swap curr->next = prev each step.

Step 4 — Algorithm:

1. prev = null, curr = head

2. While curr: save next = curr->next, set curr->next = prev, advance prev = curr, curr = next

3. Return prev (new head)

Step 5 — Edge cases: Empty or single-node list — return as is.

function reverseList(?ListNode $head): ?ListNode {
    $prev = null;
    $curr = $head;
    while ($curr !== null) {
        $next       = $curr->next;
        $curr->next = $prev;
        $prev       = $curr;
        $curr       = $next;
    }
    return $prev;
}

Time: O(n) | Space: O(1)

---

Pattern 2 — Find Middle Node (Slow/Fast Pointers)

🧠 How to Approach This

Step 1 — Recognize the pattern: Floyd's two-pointer — slow moves 1 step, fast moves 2 steps.

Step 2 — Brute force (what NOT to do): Count length, walk n/2 steps — two passes.

Step 3 — Optimal insight: When fast reaches end, slow is at the middle. One pass.

Step 4 — Algorithm:

1. slow = fast = head

2. While fast != null && fast->next != null: slow = slow->next, fast = fast->next->next

3. Return slow

Step 5 — Edge cases: Even-length list — returns second middle (standard for most problems).

function findMiddle(?ListNode $head): ?ListNode {
    $slow = $head;
    $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    return $slow;
}

Time: O(n) | Space: O(1)

---

Pattern 3 — Detect Cycle (Floyd's Algorithm)

🧠 How to Approach This

Step 1 — Recognize the pattern: If a cycle exists, fast pointer will lap slow pointer.

Step 2 — Brute force (what NOT to do): Track visited nodes in a HashSet — O(n) space.

Step 3 — Optimal insight: Floyd's cycle detection — slow+fast meet inside the cycle.

Step 4 — Algorithm:

1. slow = fast = head

2. While fast and fast->next not null: advance both; if they meet → cycle exists

3. If loop ends without meeting → no cycle

Step 5 — Edge cases: Empty list or single node without cycle → false.

function hasCycle(?ListNode $head): bool {
    $slow = $head;
    $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($slow === $fast) return true;
    }
    return false;
}

Time: O(n) | Space: O(1)

---

Pattern 4 — Merge Two Sorted Lists

🧠 How to Approach This

Step 1 — Recognize the pattern: Two-pointer merge (like merge sort's merge step).

Step 2 — Brute force (what NOT to do): Collect all values, sort, rebuild — O(n log n).

Step 3 — Optimal insight: Compare heads, attach the smaller, advance that pointer.

Step 4 — Algorithm:

1. Create dummy head

2. While both lists non-null: append the smaller node, advance its pointer

3. Append remaining nodes

4. Return dummy->next

Step 5 — Edge cases: One or both lists empty.

function mergeTwoLists(?ListNode $l1, ?ListNode $l2): ?ListNode {
    $dummy = new ListNode(0);
    $tail  = $dummy;
    while ($l1 !== null && $l2 !== null) {
        if ($l1->val <= $l2->val) {
            $tail->next = $l1;
            $l1 = $l1->next;
        } else {
            $tail->next = $l2;
            $l2 = $l2->next;
        }
        $tail = $tail->next;
    }
    $tail->next = $l1 ?? $l2;
    return $dummy->next;
}

Time: O(n + m) | Space: O(1)

---

Pattern 5 — Remove Nth Node From End

🧠 How to Approach This

Step 1 — Recognize the pattern: Two pointers with a gap of N between them.

Step 2 — Brute force (what NOT to do): Get length, calculate position, walk again — two passes.

Step 3 — Optimal insight: Advance fast pointer N+1 steps ahead; then move both until fast = null. Slow is at the node before the target.

Step 4 — Algorithm:

1. Dummy head, both pointers start at dummy

2. Advance fast N+1 steps

3. Move both until fast = null

4. slow->next = slow->next->next

Step 5 — Edge cases: Remove the head node (N = list length) — dummy handles this.

function removeNthFromEnd(?ListNode $head, int $n): ?ListNode {
    $dummy = new ListNode(0, $head);
    $slow  = $dummy;
    $fast  = $dummy;
    for ($i = 0; $i <= $n; $i++) {
        $fast = $fast->next;
    }
    while ($fast !== null) {
        $slow = $slow->next;
        $fast = $fast->next;
    }
    $slow->next = $slow->next->next;
    return $dummy->next;
}

Time: O(n) | Space: O(1)

---

Pattern 6 — Find Intersection of Two Lists

🧠 How to Approach This

Step 1 — Recognize the pattern: Two pointers that "switch" lists to equalise path lengths.

Step 2 — Brute force (what NOT to do): Store all nodes of list A in a set, traverse list B.

Step 3 — Optimal insight: Pointer A walks A then B; pointer B walks B then A. They meet at intersection after the same total distance.

Step 4 — Algorithm:

1. a = headA, b = headB

2. While a !== b: advance each, switch to other list's head on null

3. Return a (null if no intersection)

Step 5 — Edge cases: No intersection — both become null simultaneously.

function getIntersectionNode(?ListNode $headA, ?ListNode $headB): ?ListNode {
    $a = $headA;
    $b = $headB;
    while ($a !== $b) {
        $a = ($a !== null) ? $a->next : $headB;
        $b = ($b !== null) ? $b->next : $headA;
    }
    return $a;
}

Time: O(n + m) | Space: O(1)