Merge Two Sorted Lists: Combining Linked Lists in Order

The "Merge Two Sorted Lists" problem is a fundamental exercise in linked list manipulation, focusing on merging two sorted lists into one.

Problem Statement

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example

• Input: List1 1 -> 2 -> 4, List2 1 -> 3 -> 4
• Output: Merged List 1 -> 1 -> 2 -> 3 -> 4 -> 4

Iterative Solution

Breaking Down the Solution

• Initialize a Dummy Head: Start with a dummy head to simplify edge cases and maintain a reference to the head of the merged list.
• Iterate Through Both Lists: Compare nodes from both lists, appending the smaller node to the merged list.
• Handle Remaining Nodes: Once one of the lists is exhausted, attach the remaining part of the other list to the merged list.
• Return Merged List: The next of the dummy head points to the start of the merged list.

Conclusion

Merging two sorted linked lists is a common problem that demonstrates the importance of pointer manipulation in data structures. It's a key skill for many algorithms and applications involving linked lists.

Rust Solution

Rust models the entire list as Option<Box<ListNode>>, so match (l1, l2) on the tuple of both heads folds the empty cases into the (None, l2) and (l1, None) pattern arms instead of the JS version's null guards. The (Some(mut n1), Some(mut n2)) arm binds each node mut, and n1.next.take() is the load-bearing move: it lifts the tail out and leaves None in its place, satisfying the borrow checker while the same node is handed straight back with Some(n1). Because each Box owns its successor, splicing here is a genuine move of ownership rather than a shared pointer copy.

Go Solution

Go uses a raw *ListNode pointer and leans on nil for the base cases — if l1 == nil { return l2 } needs no wrapper type, and reassigning l1.next = mergeTwoLists(l1.next, l2) splices directly, with none of Rust's .take() dance, because the garbage collector owns the nodes. toSlice starts from a zero-value var v []int (a nil slice) and grows it with append, which Go happily does from nil, and it returns that nil slice rather than an empty one for an empty list. fromVec threads a var head, tail *ListNode pair through range v, linking each &ListNode{val: x} composite literal onto the tail.