Merge Lists

Merging two sorted lists and k sorted lists efficiently.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Merge Two Sorted Lists

Use dummy head + tail pointer. Compare heads, attach smaller, advance. O(n+m) time, O(1) space.

Gomerge-two-sorted-lists.go

25 linesLn 1, Col 1Go

Dummy head avoids special case for first node. Tail tracks end of merged list. Attach remaining list when one exhausts.

Merge K Sorted Lists

Three approaches: (1) Merge pairwise repeatedly O(kN), (2) Min-heap of heads O(N log k), (3) Divide and conquer O(N log k). Heap and D&C are optimal.

Gomerge-k-lists-with-min-heap.go

49 linesLn 1, Col 1Go

Heap stores (value, node) for each list head. Extract min, add to result, push next from same list. O(N log k) where N = total nodes, k = number of lists.

Merge Sorted Arrays

Given two sorted arrays, merge into first array (which has enough space). Start from end to avoid overwriting.

Gomerge-sorted-arrays-(leetcode-88).go

22 linesLn 1, Col 1Go

Three pointers from end: i for nums1, j for nums2, k for merged position. No extra space needed. Works because nums1 has buffer space at end.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.