LeetCode: Solving the 'Merge Two Sorted Lists' Problem

One of the most common LeetCode problems, and a favourite for technical interviews, is 'Merge Two Sorted Lists'. This is a problem designed to test our understanding of linked lists, recursion, and iterative merging techniques. Here, I intend to explore the problem and walk through a straightforward solution in using JavaScript (TypeScript), as well as discussing its complexity and efficiency (which are certainly extra bonus points in any interview scenario!).

Understanding the Problem

The 'Merge Two Sorted Lists' problem (LeetCode problem #21) provides two sorted linked lists. The task is simple: merge these lists into a single, sorted linked list.

Example

If we have two lists:

List 1: 1 → 3 → 5List 2: 1 → 2 → 4

Then the merged list should become:

1 → 1 → 2 → 3 → 4 → 5

The final result is a single, sorted, linked list containing all the elements from both original lists.

Solving the Problem Step‑By‑Step

This is a classic iteration problem, so the solution looks like this:

1. Create a new "dummy" node to start the merged list.
2. Iterate through both lists, comparing the values of the current nodes.
3. Attach the smaller node to the merged list and move forward.
4. Continue until one list is exhausted, then append any remaining nodes from the other list.

In JavaScript, this might look something like this:

type ListNode = {  val: number;  next: ListNode | null;};const mergeTwoLists = (  l1: ListNode | null,  l2: ListNode | null): ListNode | null => {  const dummy: ListNode = { val: 0, next: null };  let current = dummy;  while (l1 && l2) {    if (l1.val < l2.val) {      current.next = l1;      l1 = l1.next;    } else {      current.next = l2;      l2 = l2.next;    }    current = current.next;  }  current.next = l1 || l2;  return dummy.next;};

How This Works

• The dummy node allows us to handle edge cases simply (e.g., empty lists).
• At each step, we select the smaller node from either l1 or l2.
• Once we reach the end of one list, the remaining nodes from the other list are attached directly since they are already sorted.

Complexity Analysis

So far, this should all be fairly straightforward for any competent developer. In an interview or test situation, however, what might help set you apart is being able to talk about the complexity of your solution.

Time Complexity

• O(n + m)

  , where n and m are the lengths of the two lists. We iterate through each node exactly once.

Space Complexity

• O(1)

  because we reuse existing nodes and only add a dummy node, regardless of the list sizes.

Alternative Approach: Recursive Solution

Although I've used iteration above to solve this, we could also explore solving the problem recursively, although it does have some additional overhead due to extra function calls:

const mergeTwoLists = (  l1: ListNode | null,   l2: ListNode | null): ListNode | null => {  if (!l1) return l2;  if (!l2) return l1;  if (l1.val < l2.val) {    l1.next = mergeTwoLists(l1.next, l2);    return l1;  } else {    l2.next = mergeTwoLists(l1, l2.next);    return l2;  }};

In comparison, this is perhaps a more elegant and concise solution, but it also uses additional stack space, which could become significant for very large lists.

Adding Tests to Verify the Solution

I'm a strong proponent of test coverage in development, so writing tests not only ensures that our function behaves correctly and helps us catch mistakes early, but it also means that if it's me looking at your solution, this will make you stand out all the more.

This type of single‑function functionality is perfect for a few simple test cases using a testing framework like Jest.

Writing Unit Tests with Jest

When testing our mergeTwoLists functions, we need to use linked lists structured exactly like our function's output (ListNode objects), rather than plain JavaScript objects. Here's a quick example of how we might write a suitable test:

test('merges two sorted lists correctly', () => {  const list1: ListNode = { val: 1, next: { val: 3, next: { val: 5, next: null } } };  const list2: ListNode = { val: 1, next: { val: 2, next: { val: 4, next: null } } };  const expected: ListNode = {    val: 1,    next: {      val: 1,      next: {        val: 2,        next: {          val: 3,          next: {            val: 4,            next: {              val: 5,              next: null,            },          },        },      },    },  };  expect(mergeTwoLists(list1, list2)).toEqual(expected);});

Practical Tips for Solving Linked List Problems

• Use a dummy node to simplify pointer manipulation and avoid edge case checks.
• Always consider both iterative and recursive solutions, but prefer the iterative version for large datasets to avoid potential stack overflow issues.
• Drawing a diagram helps visualise node manipulation, reducing the chance of mistakes.

Wrapping up

The 'Merge Two Sorted Lists' problem is a good introduction to managing linked list pointers and merging sorted data. By practising problems like this, we improve our understanding of linked lists, pointer manipulation, and basic algorithm design, strengthening our broader problem‑solving skills.

Key Takeaways

• The problem requires merging two sorted linked lists into one sorted list.
• An iterative approach using a dummy node simplifies edge cases.
• The solution has a linear time complexity (O(n + m)) and constant space complexity (O(1)).
• Recursive solutions are elegant but may be less practical for larger datasets.
• Visualising list operations helps to reduce errors and improve code clarity.

Mastering problems like this not only builds confidence for coding interviews but also improves overall understanding of linked‑list manipulation.