Merging two sorted linked lists is a common problem in algorithms that involves combining two lists into a single sorted list. The problem is straightforward when you understand the basic principles of linked lists and sorting. Let’s break down the problem step by step, provide an example, and show how to implement the solution in various programming languages.

Understanding the Problem

Objective: Given two linked lists that are each sorted in ascending order, merge them into a single linked list that is also sorted in ascending order.

Steps to Solve the Problem

  1. Initialize Pointers: Use pointers to traverse both linked lists. You’ll also need a pointer to build the merged list.
  2. Compare Nodes: Compare the values of the nodes from the two lists. Append the smaller node to the merged list and move the pointer forward in that list.
  3. Handle Remaining Nodes: Once one of the lists is fully traversed, append the remaining nodes from the other list to the merged list.
  4. Return the Merged List: Ensure that the merged list is properly linked and return it.

Example

Consider two linked lists:

  • List 1: 1 → 3 → 5
  • List 2: 2 → 4 → 6

Merged List: 1 → 2 → 3 → 4 → 5 → 6

Detailed Steps

  1. Initialize Pointers:
  • Use a dummy node to simplify the merging process.
  • current pointer starts at the dummy node and will be used to build the merged list.
  1. Compare Nodes:
  • Compare the head nodes of both lists. Append the smaller node to the current node of the merged list.
  1. Handle Remaining Nodes:
  • Once one list is exhausted, append the remaining nodes of the other list to the merged list.
  1. Return the Merged List:
  • Skip the dummy node to get the head of the merged list.
See also  How do you reverse an array?

Code Examples

1. Python

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def merge_two_sorted_lists(l1, l2):
    dummy = ListNode()
    current = dummy

    while l1 and l2:
        if l1.value < l2.value:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    # Append the remaining nodes of l1 or l2
    if l1:
        current.next = l1
    else:
        current.next = l2

    return dummy.next

# Helper function to create a linked list from a list for testing
def create_linked_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for value in values[1:]:
        current.next = ListNode(value)
        current = current.next
    return head

# Example usage
l1 = create_linked_list([1, 3, 5])
l2 = create_linked_list([2, 4, 6])
merged_list = merge_two_sorted_lists(l1, l2)

# Print merged list
while merged_list:
    print(merged_list.value, end=" -> ")
    merged_list = merged_list.next

2. JavaScript

class ListNode {
    constructor(value = 0, next = null) {
        this.value = value;
        this.next = next;
    }
}

function mergeTwoSortedLists(l1, l2) {
    let dummy = new ListNode();
    let current = dummy;

    while (l1 && l2) {
        if (l1.value < l2.value) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    // Append the remaining nodes of l1 or l2
    current.next = l1 || l2;

    return dummy.next;
}

// Helper function to create a linked list from an array for testing
function createLinkedList(arr) {
    if (arr.length === 0) return null;
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

// Example usage
let l1 = createLinkedList([1, 3, 5]);
let l2 = createLinkedList([2, 4, 6]);
let mergedList = mergeTwoSortedLists(l1, l2);

// Print merged list
while (mergedList) {
    process.stdout.write(mergedList.value + " -> ");
    mergedList = mergedList.next;
}

3. Java

class ListNode {
    int value;
    ListNode next;
    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

public class Main {
    public static ListNode mergeTwoSortedLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.value < l2.value) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // Append the remaining nodes of l1 or l2
        current.next = (l1 != null) ? l1 : l2;

        return dummy.next;
    }

    // Helper function to create a linked list from an array for testing
    public static ListNode createLinkedList(int[] arr) {
        if (arr.length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.length; i++) {
            current.next = new ListNode(arr[i]);
            current = current.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode l1 = createLinkedList(new int[]{1, 3, 5});
        ListNode l2 = createLinkedList(new int[]{2, 4, 6});
        ListNode mergedList = mergeTwoSortedLists(l1, l2);

        // Print merged list
        while (mergedList != null) {
            System.out.print(mergedList.value + " -> ");
            mergedList = mergedList.next;
        }
    }
}

4. C++

#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int val) : value(val), next(nullptr) {}
};

ListNode* mergeTwoSortedLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* current = &dummy;

    while (l1 != nullptr && l2 != nullptr) {
        if (l1->value < l2->value) {
            current->next = l1;
            l1 = l1->next;
        } else {
            current->next = l2;
            l2 = l2->next;
        }
        current = current->next;
    }

    // Append the remaining nodes of l1 or l2
    current->next = (l1 != nullptr) ? l1 : l2;

    return dummy.next;
}

// Helper function to create a linked list from an array for testing
ListNode* createLinkedList(const std::vector<int>& arr) {
    if (arr.empty()) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (size_t i = 1; i < arr.size(); ++i) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

int main() {
    std::vector<int> arr1 = {1, 3, 5};
    std::vector<int> arr2 = {2, 4, 6};

    ListNode* l1 = createLinkedList(arr1);
    ListNode* l2 = createLinkedList(arr2);
    ListNode* mergedList = mergeTwoSortedLists(l1, l2);

    // Print merged list
    while (mergedList != nullptr) {
        std::cout << mergedList->value << " -> ";
        mergedList = mergedList->next;
    }
    std::cout << "nullptr" << std::endl;

    // Clean up memory
    while (l1) {
        ListNode* temp = l1;
        l1 = l1->next;
        delete temp;
    }
    while (l2) {
        ListNode* temp = l2;
        l2 = l2->next;
        delete temp;
    }
    while (mergedList) {
        ListNode* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}

5. C

using System;

class ListNode {
    public int Value;
    public ListNode Next;
    public ListNode(int value) {
        Value = value;
        Next =

 null;
    }
}

class Program {
    public static ListNode MergeTwoSortedLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (l1 != null && l2 != null) {
            if (l1.Value < l2.Value) {
                current.Next = l1;
                l1 = l1.Next;
            } else {
                current.Next = l2;
                l2 = l2.Next;
            }
            current = current.Next;
        }

        // Append the remaining nodes of l1 or l2
        current.Next = (l1 != null) ? l1 : l2;

        return dummy.Next;
    }

    // Helper function to create a linked list from an array for testing
    public static ListNode CreateLinkedList(int[] arr) {
        if (arr.Length == 0) return null;
        ListNode head = new ListNode(arr[0]);
        ListNode current = head;
        for (int i = 1; i < arr.Length; i++) {
            current.Next = new ListNode(arr[i]);
            current = current.Next;
        }
        return head;
    }

    static void Main() {
        ListNode l1 = CreateLinkedList(new int[]{1, 3, 5});
        ListNode l2 = CreateLinkedList(new int[]{2, 4, 6});
        ListNode mergedList = MergeTwoSortedLists(l1, l2);

        // Print merged list
        while (mergedList != null) {
            Console.Write(mergedList.Value + " -> ");
            mergedList = mergedList.Next;
        }
        Console.WriteLine("null");
    }
}

To merge two sorted linked lists:

  1. Initialize a dummy node and a pointer to build the merged list.
  2. Compare nodes from both lists and attach the smaller node to the merged list.
  3. Append remaining nodes from the non-exhausted list.
  4. Return the merged list, skipping the dummy node.
See also  How do you find the non-matching characters in a string?

The provided code examples in Python, JavaScript, Java, C++, and C# illustrate how to perform these steps and merge the lists efficiently.

facebookShare on Facebook
TwitterPost on X
FollowFollow us
PinterestSave

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *