Merge Two Sorted Lists Solution for Capgemini

Company: Capgemini · Difficulty: Easy · Topics: Linked List, Two Pointers

Problem Statement

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.

Examples

Example 1:

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

Output: [1,1,2,3,4,4]

Explanation: The merged list contains all nodes from both lists in sorted order.

Example 2:

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

Output: [0]

Explanation: Since list1 is empty, the merged list is just list2.

Example 3:

Input: list1 = [], list2 = []

Output: []

Explanation: Both lists are empty, so the merged list is also empty.

Example 4:

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

Output: [1,2,3,4,5,6]

Explanation: The lists are merged in alternating order.

Intuition

Since both lists are already sorted, we can merge them efficiently by comparing the values at the current positions of both lists and choosing the smaller one to add to our result.

The key insight is:

1. Compare the current nodes of both lists

2. Choose the smaller value and move that pointer forward

3. Continue until one list is exhausted

4. Append the remaining nodes from the other list

Approach

Approach 1: Iterative with Dummy Node (Optimal)

1. Create a dummy node to simplify the merging process

2. Use a current pointer to build the merged list

3. While both lists have nodes:

• Compare the values and choose the smaller one
• Attach it to the current pointer
• Move the chosen list's pointer forward

4. Attach the remaining nodes from the non-empty list

5. Return dummy->next

Approach 2: Recursive Approach

1. Base case: if one list is null, return the other

2. Compare the heads of both lists

3. Choose the smaller head and recursively merge the rest

4. Return the chosen head with its next pointing to the merged result

Approach 3: In-place Merging

1. Use one list as the base and merge the other into it

2. More complex but saves some memory

Dry Run

Let's trace through Example 1: list1 = [1,2,4], list2 = [1,3,4]

Iterative Approach:

• Initial: dummy = 0, current = dummy
• list1 = 1, list2 = 1: choose 1 from list1
• current->next = list1, current = 1, list1 = 2
• list1 = 2, list2 = 1: choose 1 from list2
• current->next = list2, current = 1, list2 = 3
• list1 = 2, list2 = 3: choose 2 from list1
• current->next = list1, current = 2, list1 = 4
• list1 = 4, list2 = 3: choose 3 from list2
• current->next = list2, current = 3, list2 = 4
• list1 = 4, list2 = 4: choose 4 from list1
• current->next = list1, current = 4, list1 = null
• list1 is null, attach remaining list2: current->next = 4
• Result: 1->1->2->3->4->4

Key Insights

1. Sorted Property: Both lists are sorted, so we can merge efficiently

2. Dummy Node: Using a dummy node simplifies the merging process

3. Pointer Manipulation: We reuse existing nodes by adjusting pointers

4. Remaining Nodes: After one list is exhausted, we can directly attach the remaining nodes

Edge Cases

1. Empty lists: Handle null inputs properly

2. One empty list: Return the non-empty list

3. Different lengths: Handle when one list is longer than the other

4. Equal values: Handle when both lists have the same value

Time and Space Complexity

• Time Complexity: O(n + m) - we visit each node exactly once
• Space Complexity: O(1) - we only use a constant amount of extra space (dummy node)

More Capgemini coding questions