🎯 PHP Linked List — Top 25 Interview Questions
Q1 — Reverse Linked List
🧠 How to Approach This
Step 1 — Recognize the pattern: Pointer reversal — must track prev, curr, next simultaneously.
Step 2 — Brute force (what NOT to do): Push to array, rebuild reversed — O(n) space.
Step 3 — Optimal insight: Iteratively flip each
curr->next = previn one pass.Step 4 — Algorithm:
1.
prev = null,curr = head2. Each step: save next, flip pointer, advance both
3. Return prev
Step 5 — Edge cases: Empty list or one node → 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)
Q2 — Find Middle of Linked List
🧠 How to Approach This
Step 1 — Recognize the pattern: Slow/fast pointer — fast moves 2x speed.
Step 2 — Brute force (what NOT to do): Count length, walk n/2 again — two passes.
Step 3 — Optimal insight: When fast hits end, slow is at middle. One pass.
Step 4 — Algorithm:
1. slow = fast = head
2. While fast && fast->next: slow++, fast += 2
3. Return slow
Step 5 — Edge cases: Even length — returns second middle (LeetCode 876).
function middleNode(?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)
Q3 — Detect Cycle (Floyd's Algorithm)
🧠 How to Approach This
Step 1 — Recognize the pattern: If a cycle exists, the fast pointer will eventually catch the slow pointer.
Step 2 — Brute force (what NOT to do): Store every visited node in a set — O(n) space.
Step 3 — Optimal insight: Floyd's cycle detection: slow moves +1, fast moves +2. They must meet if cycle exists.
Step 4 — Algorithm:
1. slow = fast = head
2. Advance both; if they meet → cycle
3. Loop ends naturally → no cycle
Step 5 — Edge cases: Null 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)
Q4 — Find Cycle Start Node
🧠 How to Approach This
Step 1 — Recognize the pattern: After Floyd's meeting point, reset one pointer to head and walk both at speed 1 — they meet at cycle start.
Step 2 — Brute force (what NOT to do): Track all visited nodes in a hash set.
Step 3 — Optimal insight: Mathematical proof: distance from head to cycle start equals distance from meeting point to cycle start.
Step 4 — Algorithm:
1. Detect meeting point (Floyd's)
2. Reset slow = head, keep fast at meeting point
3. Move both at speed 1 — they meet at cycle start
Step 5 — Edge cases: No cycle → return null.
function detectCycle(?ListNode $head): ?ListNode {
$slow = $head;
$fast = $head;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next;
$fast = $fast->next->next;
if ($slow === $fast) {
$slow = $head;
while ($slow !== $fast) {
$slow = $slow->next;
$fast = $fast->next;
}
return $slow;
}
}
return null;
}Time: O(n) | Space: O(1)
Q5 — Merge Two Sorted Lists
🧠 How to Approach This
Step 1 — Recognize the pattern: Two-pointer merge like merge sort's combine 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 smaller, advance that pointer — O(n+m).
Step 4 — Algorithm:
1. Dummy head
2. While both non-null: attach smaller, advance it
3. Attach remaining tail
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)
Q6 — Remove Nth Node From End
🧠 How to Approach This
Step 1 — Recognize the pattern: Two pointers with N+1 gap so slow stops before target.
Step 2 — Brute force (what NOT to do): Two passes — count length then walk.
Step 3 — Optimal insight: Gap of N+1 between pointers, one pass.
Step 4 — Algorithm:
1. Dummy head, fast advances N+1 steps
2. Move both until fast = null
3. Skip slow->next
Step 5 — Edge cases: Remove first node (N = length) — dummy handles it.
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)
Q7 — Delete Node (No Head Given)
🧠 How to Approach This
Step 1 — Recognize the pattern: Can't delete the node itself — copy next node's value then skip next.
Step 2 — Brute force (what NOT to do): Traverse from head to find previous node — but head isn't given.
Step 3 — Optimal insight: Copy next->val into current node, then delete next node.
Step 4 — Algorithm:
1. node->val = node->next->val
2. node->next = node->next->next
Step 5 — Edge cases: Guaranteed node is not the tail (per LeetCode 237 constraints).
function deleteNode(ListNode $node): void {
$node->val = $node->next->val;
$node->next = $node->next->next;
}Time: O(1) | Space: O(1)
Q8 — Intersection of Two Linked Lists
🧠 How to Approach This
Step 1 — Recognize the pattern: Two pointers that traverse both lists in sequence cancel out the length difference.
Step 2 — Brute force (what NOT to do): Store all nodes of A in a set, traverse B — O(n) space.
Step 3 — Optimal insight: a walks A→B, b walks B→A. Total distance same → meet at intersection.
Step 4 — Algorithm:
1. a = headA, b = headB
2. Advance; switch to other head on null
3. Return when a === b
Step 5 — Edge cases: No intersection — both reach null together.
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)
Q9 — Palindrome Linked List
🧠 How to Approach This
Step 1 — Recognize the pattern: Find middle, reverse second half, compare with first half.
Step 2 — Brute force (what NOT to do): Convert to array, two-pointer check — O(n) space.
Step 3 — Optimal insight: Slow/fast to find middle, reverse in-place, compare — O(1) space.
Step 4 — Algorithm:
1. Find middle (slow/fast)
2. Reverse from middle onward
3. Compare first half with reversed second half
Step 5 — Edge cases: Odd vs even length — slow/fast handles both.
function isPalindrome(?ListNode $head): bool {
// Find middle
$slow = $head; $fast = $head;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next;
$fast = $fast->next->next;
}
// Reverse second half
$prev = null; $curr = $slow;
while ($curr !== null) {
$next = $curr->next; $curr->next = $prev; $prev = $curr; $curr = $next;
}
// Compare
$left = $head; $right = $prev;
while ($right !== null) {
if ($left->val !== $right->val) return false;
$left = $left->next; $right = $right->next;
}
return true;
}Time: O(n) | Space: O(1)
Q10 — Remove Duplicates from Sorted List
🧠 How to Approach This
Step 1 — Recognize the pattern: Skip nodes with duplicate values while traversing.
Step 2 — Brute force (what NOT to do): Use a hash set to track seen values — O(n) space.
Step 3 — Optimal insight: Since sorted, duplicates are adjacent. Skip with
curr->next = curr->next->nextwhen equal.Step 4 — Algorithm:
1. curr = head
2. While curr && curr->next: if equal skip next, else advance
Step 5 — Edge cases: All same values, single node.
function deleteDuplicates(?ListNode $head): ?ListNode {
$curr = $head;
while ($curr !== null && $curr->next !== null) {
if ($curr->val === $curr->next->val) {
$curr->next = $curr->next->next;
} else {
$curr = $curr->next;
}
}
return $head;
}Time: O(n) | Space: O(1)
Q11 — Rotate List by K
🧠 How to Approach This
Step 1 — Recognize the pattern: Form a ring, find new tail at position (len - k%len - 1).
Step 2 — Brute force (what NOT to do): Rotate one step at a time — O(n·k).
Step 3 — Optimal insight: Connect tail to head, walk to new tail, cut.
Step 4 — Algorithm:
1. Get length and connect tail to head (ring)
2. k = k % len; new tail is at len-k-1 steps from head
3. New head = newTail->next; newTail->next = null
Step 5 — Edge cases: k = 0, k is multiple of len → no rotation needed.
function rotateRight(?ListNode $head, int $k): ?ListNode {
if ($head === null || $head->next === null || $k === 0) return $head;
$len = 1; $tail = $head;
while ($tail->next !== null) { $tail = $tail->next; $len++; }
$tail->next = $head; // make ring
$k = $k % $len;
$stepsToNewTail = $len - $k - 1;
$newTail = $head;
for ($i = 0; $i < $stepsToNewTail; $i++) $newTail = $newTail->next;
$newHead = $newTail->next;
$newTail->next = null;
return $newHead;
}Time: O(n) | Space: O(1)
Q12 — Add Two Numbers (Lists)
🧠 How to Approach This
Step 1 — Recognize the pattern: Digit-by-digit addition with carry, numbers stored in reverse order.
Step 2 — Brute force (what NOT to do): Convert to integers, add, convert back — overflow risk with huge numbers.
Step 3 — Optimal insight: Simulate school addition: sum digits + carry, move both pointers.
Step 4 — Algorithm:
1. carry = 0, dummy head
2. While either list or carry remains: sum = l1->val + l2->val + carry; append sum%10; carry = sum/10
Step 5 — Edge cases: Lists of different length; leftover carry at the end.
function addTwoNumbers(?ListNode $l1, ?ListNode $l2): ?ListNode {
$dummy = new ListNode(0);
$curr = $dummy;
$carry = 0;
while ($l1 !== null || $l2 !== null || $carry > 0) {
$sum = ($l1?->val ?? 0) + ($l2?->val ?? 0) + $carry;
$carry = intdiv($sum, 10);
$curr->next = new ListNode($sum % 10);
$curr = $curr->next;
$l1 = $l1?->next;
$l2 = $l2?->next;
}
return $dummy->next;
}Time: O(max(n,m)) | Space: O(max(n,m))
Q13 — Copy List with Random Pointer
🧠 How to Approach This
Step 1 — Recognize the pattern: Deep copy where each node has an extra random pointer to any node.
Step 2 — Brute force (what NOT to do): Two passes with a hash map — O(n) space.
Step 3 — Optimal insight: Interleave cloned nodes in original list, set randoms, then separate.
Step 4 — Algorithm:
1. Insert clone after each original node
2. Set clone->random = original->random->next
3. Separate the two lists
Step 5 — Edge cases: Random pointer is null; single node.
class NodeWithRandom {
public int $val;
public ?NodeWithRandom $next = null;
public ?NodeWithRandom $random = null;
public function __construct(int $val) { $this->val = $val; }
}
function copyRandomList(?NodeWithRandom $head): ?NodeWithRandom {
if ($head === null) return null;
// Step 1: interleave clones
$curr = $head;
while ($curr !== null) {
$clone = new NodeWithRandom($curr->val);
$clone->next = $curr->next;
$curr->next = $clone;
$curr = $clone->next;
}
// Step 2: set randoms
$curr = $head;
while ($curr !== null) {
if ($curr->random !== null) $curr->next->random = $curr->random->next;
$curr = $curr->next->next;
}
// Step 3: separate
$dummy = new NodeWithRandom(0);
$cloneTail = $dummy;
$curr = $head;
while ($curr !== null) {
$cloneTail->next = $curr->next;
$curr->next = $curr->next->next;
$cloneTail = $cloneTail->next;
$curr = $curr->next;
}
return $dummy->next;
}Time: O(n) | Space: O(1) extra (excluding output)
Q14 — Sort Linked List (Merge Sort)
🧠 How to Approach This
Step 1 — Recognize the pattern: Merge sort on linked list — O(1) merge space, ideal for LL.
Step 2 — Brute force (what NOT to do): Collect values, sort array, rebuild — O(n) space.
Step 3 — Optimal insight: Find middle, split, recursive sort, merge — O(n log n) with O(log n) stack.
Step 4 — Algorithm:
1. Base case: null or single node
2. Find middle, split into two halves
3. Recursively sort both halves
4. Merge the sorted halves
Step 5 — Edge cases: Empty list, single node.
function sortList(?ListNode $head): ?ListNode {
if ($head === null || $head->next === null) return $head;
// Find middle
$slow = $head; $fast = $head->next;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next; $fast = $fast->next->next;
}
$mid = $slow->next;
$slow->next = null;
$left = sortList($head);
$right = sortList($mid);
return mergeTwoListsHelper($left, $right);
}
function mergeTwoListsHelper(?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 log n) | Space: O(log n) stack
Q15 — Odd Even Linked List
🧠 How to Approach This
Step 1 — Recognize the pattern: Separate odd-indexed and even-indexed nodes, then concatenate.
Step 2 — Brute force (what NOT to do): Create new list with two passes — O(n) space.
Step 3 — Optimal insight: Two running pointers leap-frog, reconnect even head after odd tail.
Step 4 — Algorithm:
1. odd = head, even = head->next, evenHead = even
2. While even && even->next: odd->next = even->next; odd = odd->next; even->next = odd->next; even = even->next
3. odd->next = evenHead
Step 5 — Edge cases: Less than 3 nodes.
function oddEvenList(?ListNode $head): ?ListNode {
if ($head === null) return null;
$odd = $head;
$even = $head->next;
$evenHead = $even;
while ($even !== null && $even->next !== null) {
$odd->next = $even->next;
$odd = $odd->next;
$even->next = $odd->next;
$even = $even->next;
}
$odd->next = $evenHead;
return $head;
}Time: O(n) | Space: O(1)
Q16 — Swap Nodes in Pairs
🧠 How to Approach This
Step 1 — Recognize the pattern: Process two nodes at a time, swap their order.
Step 2 — Brute force (what NOT to do): Collect all values into array, swap in pairs, rebuild.
Step 3 — Optimal insight: Iterative with a prev pointer, swap curr and curr->next in place.
Step 4 — Algorithm:
1. Dummy head, prev = dummy
2. While two nodes exist: swap them, advance prev by 2
Step 5 — Edge cases: Odd length — last node stays in place.
function swapPairs(?ListNode $head): ?ListNode {
$dummy = new ListNode(0, $head);
$prev = $dummy;
while ($prev->next !== null && $prev->next->next !== null) {
$first = $prev->next;
$second = $prev->next->next;
$first->next = $second->next;
$second->next = $first;
$prev->next = $second;
$prev = $first;
}
return $dummy->next;
}Time: O(n) | Space: O(1)
Q17 — Reverse Linked List II (Left to Right)
🧠 How to Approach This
Step 1 — Recognize the pattern: Reverse a sublist between positions left and right in one pass.
Step 2 — Brute force (what NOT to do): Extract sublist, reverse separately, reattach — messy.
Step 3 — Optimal insight: Walk to position left-1, then use insertion-at-front technique for the sublist.
Step 4 — Algorithm:
1. Dummy head, walk to node before position left
2. Insert each subsequent node at the front of the reversed segment
Step 5 — Edge cases: left = right (no reversal), left = 1 (starts at head).
function reverseBetween(?ListNode $head, int $left, int $right): ?ListNode {
$dummy = new ListNode(0, $head);
$prev = $dummy;
for ($i = 0; $i < $left - 1; $i++) $prev = $prev->next;
$curr = $prev->next;
for ($i = 0; $i < $right - $left; $i++) {
$next = $curr->next;
$curr->next = $next->next;
$next->next = $prev->next;
$prev->next = $next;
}
return $dummy->next;
}Time: O(n) | Space: O(1)
Q18 — LRU Cache
🧠 How to Approach This
Step 1 — Recognize the pattern: O(1) get and put requires hash map + doubly linked list.
Step 2 — Brute force (what NOT to do): Sorted array tracking access times — O(n) operations.
Step 3 — Optimal insight: HashMap for O(1) lookup + DLL for O(1) move-to-front and remove-from-back.
Step 4 — Algorithm:
1. HashMap: key → DLL node
2. Get: move node to front, return value
3. Put: if exists update & move front; if new add front; if over capacity remove tail
Step 5 — Edge cases: Capacity = 1; updating existing key.
class LRUNode {
public int $key, $val;
public ?LRUNode $prev = null, $next = null;
public function __construct(int $k, int $v) { $this->key = $k; $this->val = $v; }
}
class LRUCache {
private int $capacity;
private array $map = [];
private LRUNode $head, $tail;
public function __construct(int $capacity) {
$this->capacity = $capacity;
$this->head = new LRUNode(0, 0);
$this->tail = new LRUNode(0, 0);
$this->head->next = $this->tail;
$this->tail->prev = $this->head;
}
public function get(int $key): int {
if (!isset($this->map[$key])) return -1;
$this->moveToFront($this->map[$key]);
return $this->map[$key]->val;
}
public function put(int $key, int $value): void {
if (isset($this->map[$key])) {
$this->map[$key]->val = $value;
$this->moveToFront($this->map[$key]);
} else {
$node = new LRUNode($key, $value);
$this->map[$key] = $node;
$this->addToFront($node);
if (count($this->map) > $this->capacity) {
$removed = $this->removeTail();
unset($this->map[$removed->key]);
}
}
}
private function addToFront(LRUNode $node): void {
$node->next = $this->head->next;
$node->prev = $this->head;
$this->head->next->prev = $node;
$this->head->next = $node;
}
private function removeNode(LRUNode $node): void {
$node->prev->next = $node->next;
$node->next->prev = $node->prev;
}
private function moveToFront(LRUNode $node): void {
$this->removeNode($node);
$this->addToFront($node);
}
private function removeTail(): LRUNode {
$node = $this->tail->prev;
$this->removeNode($node);
return $node;
}
}Time: O(1) get/put | Space: O(capacity)
Q19 — Reorder List
🧠 How to Approach This
Step 1 — Recognize the pattern: 1→2→3→4→5 becomes 1→5→2→4→3. Interleave first and reversed second half.
Step 2 — Brute force (what NOT to do): Collect to array, reconstruct — O(n) space.
Step 3 — Optimal insight: (1) Find middle (2) Reverse second half (3) Merge alternating.
Step 4 — Algorithm:
1. Find middle with slow/fast
2. Reverse from middle->next
3. Interleave: alternate between first and second half nodes
Step 5 — Edge cases: Even vs odd length.
function reorderList(?ListNode $head): void {
if ($head === null || $head->next === null) return;
// Find middle
$slow = $head; $fast = $head;
while ($fast->next !== null && $fast->next->next !== null) {
$slow = $slow->next; $fast = $fast->next->next;
}
// Reverse second half
$prev = null; $curr = $slow->next; $slow->next = null;
while ($curr !== null) {
$next = $curr->next; $curr->next = $prev; $prev = $curr; $curr = $next;
}
// Merge
$first = $head; $second = $prev;
while ($second !== null) {
$tmp1 = $first->next; $tmp2 = $second->next;
$first->next = $second;
$second->next = $tmp1;
$first = $tmp1; $second = $tmp2;
}
}Time: O(n) | Space: O(1)
Q20 — Merge K Sorted Lists
🧠 How to Approach This
Step 1 — Recognize the pattern: Divide and conquer — merge pairs of lists repeatedly.
Step 2 — Brute force (what NOT to do): Collect all values, sort, rebuild — O(N log N) but O(N) space.
Step 3 — Optimal insight: Divide lists into pairs, merge each pair — O(N log k) time, O(1) space per merge.
Step 4 — Algorithm:
1. While more than 1 list: pair up and merge adjacent lists
2. Repeat until one list remains
Step 5 — Edge cases: Empty array, single list.
function mergeKLists(array $lists): ?ListNode {
if (empty($lists)) return null;
while (count($lists) > 1) {
$merged = [];
for ($i = 0; $i < count($lists); $i += 2) {
$l1 = $lists[$i];
$l2 = $lists[$i + 1] ?? null;
$merged[] = mergeTwoListsHelper($l1, $l2);
}
$lists = $merged;
}
return $lists[0];
}Time: O(N log k) where N = total nodes | Space: O(1)
Q21 — Reverse Nodes in K-Group
🧠 How to Approach This
Step 1 — Recognize the pattern: Reverse each group of K nodes; leave remainder if less than K.
Step 2 — Brute force (what NOT to do): Collect all to array, reverse in-place groups, rebuild.
Step 3 — Optimal insight: Repeatedly check if K nodes remain; if yes reverse that segment, advance.
Step 4 — Algorithm:
1. Count K nodes from curr; if fewer than K stop
2. Reverse K nodes
3. Connect prev group to reversed head, continue
Step 5 — Edge cases: List length not divisible by K.
function reverseKGroup(?ListNode $head, int $k): ?ListNode {
$dummy = new ListNode(0, $head);
$groupPrev = $dummy;
while (true) {
// Check k nodes exist
$kth = $groupPrev;
for ($i = 0; $i < $k; $i++) {
$kth = $kth->next;
if ($kth === null) return $dummy->next;
}
$groupNext = $kth->next;
// Reverse group
$prev = $groupNext;
$curr = $groupPrev->next;
while ($curr !== $groupNext) {
$next = $curr->next;
$curr->next = $prev;
$prev = $curr;
$curr = $next;
}
$tmp = $groupPrev->next;
$groupPrev->next = $kth;
$groupPrev = $tmp;
}
}Time: O(n) | Space: O(1)
Q22 — Linked List Cycle II (Return Position)
Already covered in Q4. See Find Cycle Start Node.
Q23 — Maximum Twin Sum
🧠 How to Approach This
Step 1 — Recognize the pattern: Twin sum = node i + node (n-1-i). Find middle, reverse second half, sum pairs.
Step 2 — Brute force (what NOT to do): Convert to array, sum pairs — O(n) extra space.
Step 3 — Optimal insight: Reverse second half in-place, walk from both ends simultaneously.
Step 4 — Algorithm:
1. Find middle (slow/fast)
2. Reverse second half from middle->next
3. Walk both halves, track max twin sum
Step 5 — Edge cases: Even length guaranteed by problem.
function pairSum(?ListNode $head): int {
// Find middle
$slow = $head; $fast = $head;
while ($fast !== null && $fast->next !== null) {
$slow = $slow->next; $fast = $fast->next->next;
}
// Reverse second half
$prev = null; $curr = $slow;
while ($curr !== null) {
$next = $curr->next; $curr->next = $prev; $prev = $curr; $curr = $next;
}
// Find max twin sum
$max = 0; $left = $head; $right = $prev;
while ($right !== null) {
$max = max($max, $left->val + $right->val);
$left = $left->next;
$right = $right->next;
}
return $max;
}Time: O(n) | Space: O(1)
Q24 — Flatten Multilevel Doubly Linked List
🧠 How to Approach This
Step 1 — Recognize the pattern: DFS — when a child exists, splice child list between current and next.
Step 2 — Brute force (what NOT to do): Recursive with stack tracking — harder to manage.
Step 3 — Optimal insight: Iterative: when curr has a child, insert child list inline.
Step 4 — Algorithm:
1. Walk curr; when child found: find child's tail
2. Connect curr → child, child's tail → curr's next; clear child pointer
Step 5 — Edge cases: Multiple levels deep; tail nodes.
class MLNode {
public int $val;
public ?MLNode $next = null, $prev = null, $child = null;
public function __construct(int $val) { $this->val = $val; }
}
function flatten(?MLNode $head): ?MLNode {
$curr = $head;
while ($curr !== null) {
if ($curr->child !== null) {
$child = $curr->child;
$next = $curr->next;
// Find tail of child list
$childTail = $child;
while ($childTail->next !== null) $childTail = $childTail->next;
// Connect
$curr->next = $child;
$child->prev = $curr;
$childTail->next = $next;
if ($next !== null) $next->prev = $childTail;
$curr->child = null;
}
$curr = $curr->next;
}
return $head;
}Time: O(n) | Space: O(1)
Q25 — Split Linked List in Parts
🧠 How to Approach This
Step 1 — Recognize the pattern: Divide list into k parts; larger parts come first (greedy distribution).
Step 2 — Brute force (what NOT to do): Convert to array, split, rebuild.
Step 3 — Optimal insight: base = len/k, extra = len%k. First
extraparts get base+1 nodes.Step 4 — Algorithm:
1. Get length
2. base = len/k, extra = len%k
3. Walk list, cut at each part boundary
Step 5 — Edge cases: k > len (some parts are null); k = 1.
function splitListToParts(?ListNode $head, int $k): array {
$len = 0; $curr = $head;
while ($curr !== null) { $len++; $curr = $curr->next; }
$base = intdiv($len, $k);
$extra = $len % $k;
$result = [];
$curr = $head;
for ($i = 0; $i < $k; $i++) {
$result[] = $curr;
$partSize = $base + ($i < $extra ? 1 : 0);
for ($j = 0; $j < $partSize - 1 && $curr !== null; $j++) $curr = $curr->next;
if ($curr !== null) { $next = $curr->next; $curr->next = null; $curr = $next; }
}
return $result;
}Time: O(n + k) | Space: O(k)