LeetCode #21: Merge Two Sorted Lists — Solved in Java

Dummy Head Merge and In-Place Stitch with Pointer Flipping

Image Source

Merging two sorted linked lists is a classic coding problem that shows up often in interviews and practice sets like LeetCode. The inputs are two lists where the values are already sorted in non-decreasing order, and the goal is to merge them into a single sorted list without adding any new data nodes, though some solutions bring in a one-node dummy sentinel to keep the pointer logic easier to follow. The challenge isn’t in sorting, because both inputs are sorted already, but in managing pointers so that the final list preserves order while staying efficient in both time and space.

One way to frame the problem is to imagine two runners moving through their lists. At every step you decide which runner is carrying the smaller value and attach that node next in the result. That process continues until one runner finishes, at which point the rest of the other list can be stitched in place without any further checks. The problem is simple but allows for different strategies, and comparing those strategies shows how small design choices can make a solution easier to write, or in some cases, more attractive in an interview.

LeetCode: Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].

• -100 <= Node.val <= 100

• Both list1 and list2 are sorted in non-decreasing order.

Solution 1: Simple Dummy Head Merge

This method walks two pointers across the input lists and builds the result by always taking the smaller node next. A tiny sentinel node keeps the code simple and avoids edge checks for the first insert.