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.