Sort a Linked List Using Merge Sort in DSA Python - Build from Scratch

Sort a Linked List Using Merge Sort

📖 Scenario: You are working on a contact list app. The contacts are stored in a linked list, but they are not sorted by name. You want to sort the contacts alphabetically to make searching easier.

🎯 Goal: Build a program that sorts a singly linked list of contact names using the merge sort algorithm.

📋 What You'll Learn

Create a singly linked list with given contact names

Implement a function to split the linked list into halves

Implement a function to merge two sorted linked lists

Implement merge sort to sort the linked list by contact names

Print the sorted linked list

💡 Why This Matters

🌍 Real World

Sorting linked lists is useful in applications like contact management, where data is stored in linked lists and needs to be ordered for quick search and display.

💼 Career

Understanding linked list sorting algorithms like merge sort is important for software engineers working with low-level data structures, memory-efficient algorithms, and interview coding challenges.

1

Create the Linked List

Create a class called Node with attributes name and next. Then create a linked list with these exact contact names in order: 'John', 'Alice', 'Bob', 'Diana', 'Charlie'. Store the head node in a variable called head.

DSA Python

# Define Node class and create linked list with given names
# Your code here

Hint

Define the Node class first. Then link nodes by setting the next attribute.

2

Add a Function to Split the List

Add a function called split_list that takes head of a linked list and returns two heads: left and right. Use the slow and fast pointer technique to find the middle and split the list into two halves.

DSA Python

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

head = Node('John')
head.next = Node('Alice')
head.next.next = Node('Bob')
head.next.next.next = Node('Diana')
head.next.next.next.next = Node('Charlie')

# Define split_list function below
# Your code here

Hint

Use two pointers: slow moves one step, fast moves two steps. When fast reaches the end, slow is at middle.

3

Add Merge and Merge Sort Functions

Add a function called merge_sorted_lists that takes two sorted linked lists left and right and merges them into one sorted list by name. Then add a function called merge_sort that takes head of a linked list and returns the sorted linked list using merge sort. Use split_list and merge_sorted_lists inside merge_sort.

DSA Python

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

head = Node('John')
head.next = Node('Alice')
head.next.next = Node('Bob')
head.next.next.next = Node('Diana')
head.next.next.next.next = Node('Charlie')

def split_list(head):
    if head is None or head.next is None:
        return head, None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    left = head
    right = slow.next
    slow.next = None
    return left, right

# Define merge_sorted_lists and merge_sort functions below
# Your code here

Hint

Merge two sorted lists by comparing name values. Use recursion for merge sort.

4

Print the Sorted Linked List

Use the merge_sort function to sort the linked list starting at head. Then print the sorted list names in order separated by -> and ending with null.

DSA Python

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

head = Node('John')
head.next = Node('Alice')
head.next.next = Node('Bob')
head.next.next.next = Node('Diana')
head.next.next.next.next = Node('Charlie')

def split_list(head):
    if head is None or head.next is None:
        return head, None
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    left = head
    right = slow.next
    slow.next = None
    return left, right

def merge_sorted_lists(left, right):
    if left is None:
        return right
    if right is None:
        return left
    if left.name <= right.name:
        result = left
        result.next = merge_sorted_lists(left.next, right)
    else:
        result = right
        result.next = merge_sorted_lists(left, right.next)
    return result

def merge_sort(head):
    if head is None or head.next is None:
        return head
    left, right = split_list(head)
    left = merge_sort(left)
    right = merge_sort(right)
    return merge_sorted_lists(left, right)

# Sort the linked list and print the sorted names
# Your code here

Hint

Call merge_sort(head) to get the sorted list head. Then loop through the list to collect names and print them joined by -> ending with null.