Why Merge Two Sorted Linked Lists in DSA Python?

The Big Idea

What if you could combine two sorted lists perfectly without lifting a finger?

The Scenario

Imagine you have two lists of names sorted alphabetically on paper. You want to combine them into one big sorted list. Doing this by hand means checking each name one by one, comparing, and writing them down in order.

The Problem

Manually merging two sorted lists is slow and tiring. You can easily lose track of which name comes next or accidentally skip or repeat names. It's hard to keep the order perfect without making mistakes.

The Solution

Using the "Merge Two Sorted Lists" method, a computer can quickly and correctly combine two sorted lists by comparing their first items and picking the smaller one step-by-step. This keeps the order intact and avoids mistakes.

Before vs After

✗ Before

list1 = ['Alice', 'Charlie', 'Emma']
list2 = ['Bob', 'David', 'Frank']
merged = []
# Manually compare and add each element one by one

✓ After

def merge_lists(list1, list2):
    # Automatically merge two sorted lists
    merged = []
    i = j = 0
    while i < len(list1) and j < len(list2):
        if list1[i] < list2[j]:
            merged.append(list1[i])
            i += 1
        else:
            merged.append(list2[j])
            j += 1
    merged.extend(list1[i:])
    merged.extend(list2[j:])
    return merged

What It Enables

This concept lets us combine sorted data quickly and correctly, which is key for many fast and efficient programs.

Real Life Example

When you get two sorted contact lists from different phones and want to combine them into one sorted list without duplicates or mistakes.

Key Takeaways

Merging by hand is slow and error-prone.

Automated merging compares and picks elements step-by-step.

This keeps the combined list sorted and accurate.

Practice

1. What is the main goal when merging two sorted linked lists?

easy

A. To create a new sorted linked list containing all elements from both lists

B. To reverse the order of elements in both lists

C. To find the largest element in both lists

D. To delete duplicate elements from both lists

Solution

1. Step 1: Understand the merging process

   Merging two sorted linked lists means combining them into one list that keeps the sorted order.

2. Step 2: Identify the goal

   The goal is to have a new linked list that contains all elements from both lists in sorted order.

3. Final Answer:

   To create a new sorted linked list containing all elements from both lists -> Option A

4. Quick Check:

   Merging = combine sorted lists [OK]

Hint: Merging keeps order and combines all elements [OK]

Common Mistakes:

• Thinking merging reverses lists
• Only finding largest element
• Removing duplicates instead of merging

2. Which of the following is the correct way to start merging two sorted linked lists in Python?

easy

A. def mergeLists(l1, l2):
current = ListNode(0)
dummy = current.next

B. def mergeLists(l1, l2):
dummy = null
current = dummy

C. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy

D. def mergeLists(l1, l2):
dummy = ListNode(0)
current = dummy.next

Solution

1. Step 1: Initialize dummy and current nodes properly

   We create a dummy node with value 0 and set current to dummy to build the merged list.

2. Step 2: Check options for correct syntax

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy correctly creates dummy and current pointing to dummy. def mergeLists(l1, l2): dummy = ListNode(0) current = dummy.next incorrectly sets current = dummy.next which is initially None.

3. Final Answer:

   def mergeLists(l1, l2): dummy = ListNode(0) current = dummy -> Option C

4. Quick Check:

   Dummy node with value 0 starts merge [OK]

Hint: Start with dummy node value 0 and current pointing to dummy [OK]

Common Mistakes:

• Setting current to dummy.next
• Swapping dummy and current incorrectly
• Setting dummy to null

3. What will be the output linked list after merging these two sorted lists? List 1: 1 -> 3 -> 5 -> null List 2: 2 -> 4 -> 6 -> null Use the merge logic to combine them.

medium

A. 1 -> 2 -> 4 -> 3 -> 5 -> 6 -> null

B. 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

C. 2 -> 4 -> 6 -> 1 -> 3 -> 5 -> null

D. 1 -> 3 -> 5 -> 2 -> 4 -> 6 -> null

Solution

1. Step 1: Compare nodes from both lists in order

   Start with 1 (List 1) and 2 (List 2). 1 is smaller, add 1. Then compare 3 and 2, add 2. Continue comparing and adding smaller nodes.

2. Step 2: Build merged list step-by-step

   Merged list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null after adding all nodes in sorted order.

3. Final Answer:

   1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null -> Option B

4. Quick Check:

   Sorted merge combines nodes in ascending order [OK]

Hint: Pick smaller node each step to keep order [OK]

Common Mistakes:

• Appending one list fully before the other
• Mixing node order incorrectly
• Skipping nodes during merge

4. Identify the error in this merge function snippet:

def mergeLists(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
    current.next = l1 if l1 else l2
    return dummy.next

medium

A. The 'current' pointer is not moved forward inside the loop

B. The dummy node is not initialized correctly

C. The function does not handle empty input lists

D. The return statement should return 'current' instead of 'dummy.next'

Solution

1. Step 1: Check pointer updates inside the loop

   After assigning current.next, the current pointer must move forward to current.next to continue building the list.

2. Step 2: Identify missing current update

   The code misses 'current = current.next' inside the while loop, causing an infinite loop or incorrect list.

3. Final Answer:

   The 'current' pointer is not moved forward inside the loop -> Option A

4. Quick Check:

   Move current forward after linking nodes [OK]

Hint: Always move current pointer after linking a node [OK]

Common Mistakes:

• Forgetting to move current pointer
• Returning wrong node
• Not handling empty lists (though not error here)

5. Given two sorted linked lists where one list is empty and the other is 0 -> 2 -> 4 -> null, what should the merged list be?

medium

A. 0 -> null

B. null

C. 4 -> 2 -> 0 -> null

D. 0 -> 2 -> 4 -> null

Solution

1. Step 1: Understand merging with an empty list

   If one list is empty, the merged list is just the non-empty list as it is already sorted.

2. Step 2: Apply to given lists

   Since the second list is empty and the first is 0 -> 2 -> 4 -> null, the merged list remains 0 -> 2 -> 4 -> null.

3. Final Answer:

   0 -> 2 -> 4 -> null -> Option D

4. Quick Check:

   Merging with empty list returns the other list [OK]

Hint: Empty list merge returns the other list unchanged [OK]

Common Mistakes:

• Returning null when one list is empty
• Reversing the non-empty list
• Returning only the first node