Merge Two Sorted Linked Lists in DSA Python - Build from Scratch

Merge Two Sorted Linked Lists

📖 Scenario: You are working on a contact app that keeps two separate lists of contacts sorted by their ID numbers. You want to merge these two sorted lists into one sorted list so that you can show all contacts in order.

🎯 Goal: Build a program that merges two sorted linked lists into one sorted linked list.

📋 What You'll Learn

Create two sorted linked lists using the provided Node class.

Use a helper variable to track the start of the merged list.

Write the logic to merge the two sorted linked lists into one sorted linked list.

Print the merged linked list in the format: 1 -> 2 -> 3 -> null.

💡 Why This Matters

🌍 Real World

Merging sorted lists is common in apps that combine data from multiple sources, like contact lists or event schedules.

💼 Career

Understanding linked list merging is important for software engineers working on data processing, memory management, and algorithm optimization.

1

Create two sorted linked lists

Create two sorted linked lists named list1 and list2 using the Node class. list1 should contain nodes with values 1, 3, and 5. list2 should contain nodes with values 2, 4, and 6.

DSA Python

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Create list1 with nodes 1 -> 3 -> 5 -> null
# Create list2 with nodes 2 -> 4 -> 6 -> null
# Your code here

Hint

Use the Node class to link nodes by setting the next parameter.

2

Create a dummy node to start the merged list

Create a variable called dummy as a new Node with value 0. Also create a variable called current and set it equal to dummy. These will help build the merged list.

DSA Python

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

list1 = Node(1, Node(3, Node(5)))
list2 = Node(2, Node(4, Node(6)))

# Create dummy node and current pointer
# Your code here

Hint

The dummy node helps simplify merging by providing a fixed starting point.

3

Merge the two sorted linked lists

Write a while loop that runs while both list1 and list2 are not None. Inside the loop, compare list1.val and list2.val. Attach the smaller node to current.next and move that list forward. Move current forward as well. After the loop, attach the remaining nodes from list1 or list2 to current.next.

DSA Python

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

list1 = Node(1, Node(3, Node(5)))
list2 = Node(2, Node(4, Node(6)))

dummy = Node(0)
current = dummy

# Merge list1 and list2 into one sorted list
# Your code here

Hint

Use a loop to pick the smaller node each time and move pointers forward.

4

Print the merged linked list

Create a variable called node and set it to dummy.next. Use a while loop to print each node's value followed by ->. Move node to the next node each time. After the loop, print null to show the end of the list.

DSA Python

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

list1 = Node(1, Node(3, Node(5)))
list2 = Node(2, Node(4, Node(6)))

dummy = Node(0)
current = dummy

while list1 and list2:
    if list1.val < list2.val:
        current.next = list1
        list1 = list1.next
    else:
        current.next = list2
        list2 = list2.next
    current = current.next

current.next = list1 if list1 else list2

# Print the merged linked list
# Your code here

Hint

Use a loop to print each node's value followed by an arrow, then print null at the end.

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