Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

Merge Two Sorted Linked Lists (C++, Java, Python)

Jatin Chanana by Jatin Chanana
December 22, 2023
Reading Time: 9 mins read
Merge two sorted linked lists
Follow us on Google News   Subscribe to our newsletter

Linked lists are fundamental data structures in programming, providing an efficient way to organize and manipulate data. When dealing with two sorted linked lists, a common operation is joining them into a single one. In this article, we’ll learn how to merge two sorted linked lists using the recursive approach.

What is the Merge Two Sorted Lists Problem?

Just to recap, A linked list is a linear data structure in which elements are stored in nodes. Each node points to the next node in the sequence. When we say the list is sorted, it means that the elements are arranged in ascending or descending order.

Merging two sorted linked lists preserves this order, which makes it easier for search algorithms to perform efficiently. We usually find the data in two different lists and it becomes necessary to join them to work on it. Sometimes, we need to present the output in a combined way.

Here is the problem statement: We are given 2 sorted linked lists, sorted in ascending order and we have to merge them in a way that maintains the sorted order.

Let’s look at an example,

LinkedList 1 =  1→ 3→ 6

LinkedList 2 =  2→ 4→ 5

Resultant List = 1→ 2→ 3→ 4→ 5→ 6

Example of Merging two sorted linked lists

We can see the resultant list is sorted and contains the elements of both lists.

Brute Force Approach

The simplest way to solve it is by using the brute-force approach. We can create a dummy node with a value of 0 to simplify this node and merge our present lists to this in sorted order. We will iterate both lists and keep adding the elements to this node.

Here are the steps involved in this straightforward technique:

  • First of all, we will create a dummy node with a value of 0 
create a dummy node
  • Now we will create a pointer current initially pointing to the dummy node.
create a pointer current
  • Iterate until both input lists (l1 and l2) are exhausted. Compare the values of the current nodes in l1 and l2.
Compare the values of the current nodes
  • Create a new node with the smaller value and append it to the merged list.
append it to the merged list
  • After the loop, if either l1 or l2 is not exhausted, append the remaining nodes to the merged list.
  • Return dummy->next after all iterations.
Return next node of dummy

The Time Complexity of this approach is O(max(m, n)), where m and n are the sizes of both the lists.  The Space Complexity of this approach is O(max(m, n)).

Recursive Approach to Merge Two-Sorted Lists

In the recursive approach, we will use a recursion to merge two sorted linked lists. We first select the smaller of the current nodes from both lists and then recursively merge the remaining lists.

We will follow the same steps as we were following in the brute force approach. But we will use recursion to do it easily. Following are the steps involved in merging two sorted linked lists using a recursive approach:

  1. Firstly we will declare the base case for our recursive function that If either l1 or l2 is empty, return the other list
  2. Now, Compare the values of the current nodes in l1 and l2 and choose the smaller value as the current node for the merged list.
  3. If l1 has the smaller value, recursively call the recursive function with parameters l1->next and l2.
  4. If l2 has the smaller value, recursively call the recursive function with parameters l1 and l2->next.
  5. Return the current node (either l1 or l2) as the merged list.

C++ Code

Here is the C++ program to merge two sorted lists using recursion:

#include <bits/stdc++.h>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // Base cases: if either list is empty, return the other list
    if (!l1) return l2;
    if (!l2) return l1;

    // Choose the smaller value as the current node
    if (l1->val < l2->val) {
        // Recursively merge the rest of the lists starting from l1->next and l2
        l1->next = mergeTwoLists(l1->next, l2);
        return l1;
    } else {
        // Recursively merge the rest of the lists starting from l1 and l2->next
        l2->next = mergeTwoLists(l1, l2->next);
        return l2;
    }
}

int main() {
    // Example usage
    // Create sorted linked lists
    ListNode* list1 = new ListNode(1);
    list1->next = new ListNode(3);
    list1->next->next = new ListNode(6);

    ListNode* list2 = new ListNode(2);
    list2->next = new ListNode(4);
    list2->next->next = new ListNode(5);

    // Merge the lists
    ListNode* mergedList = mergeTwoLists(list1, list2);

    // Print the merged list
    while (mergedList) {
        cout << mergedList->val << " ";
        mergedList = mergedList->next;
    }

    return 0;
}

Python Code

Here is the Python program to merge two sorted linked lists:

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

def mergeTwoLists(l1, l2):
    # Create a dummy node to serve as the head of the merged list
    dummy = ListNode()
    current = dummy

    # Loop until one of the lists is empty
    while l1 and l2:
        if l1.val < l2.val:
            # Attach the current node to the smaller node from l1
            current.next = l1
            l1 = l1.next
        else:
            # Attach the current node to the smaller node from l2
            current.next = l2
            l2 = l2.next

        # Move the current pointer to the last node
        current = current.next

    # Attach the remaining nodes from the non-empty list (if any)
    if l1:
        current.next = l1
    elif l2:
        current.next = l2

    # Return the merged list starting from the dummy node's next
    return dummy.next

# Example usage
list1 = ListNode(1, ListNode(3, ListNode(6)))
list2 = ListNode(2, ListNode(4, ListNode(5)))

mergedList = mergeTwoLists(list1, list2)

# Print the merged list
while mergedList:
    print(mergedList.val, end=" ")
    mergedList = mergedList.next

Java Code

You can implement it in Java as well:

public class MergeSortedLinkedLists {
    static class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to simplify the code
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Iterate while both lists are not empty
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }

        // If one list is not empty, append the remaining nodes
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // Return the merged list starting from the next of the dummy node
        return dummy.next;
    }

    // Helper method to print the merged list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example usage
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(3);
        list1.next.next = new ListNode(6);

        ListNode list2 = new ListNode(2);
        list2.next = new ListNode(4);
        list2.next.next = new ListNode(5);

        // Merge the lists
        ListNode mergedList = mergeTwoLists(list1, list2);

        // Print the merged list
        System.out.println("Merged List:");
        printList(mergedList);
    }
}

Output:

1 2 3 4 5 6 

The time complexity of merging two sorted lists using recursion is O(n), where n is the total number of nodes in both linked lists. This is because the function processes each node exactly once, and the number of recursive calls is proportional to the total number of nodes in the input lists.

The Space Complexity is O(n) (due to the function call stack during recursion), O(1) auxiliary space.

In the end, here you can compare both approaches and see that recursive is the best one:

ApproachTime complexitySpace complexityDetails
Brute force O(max(m, n))O(max(m, n))Create a dummy node with a value of 0 to simplify this node and merge our present lists to this in sorted order.
Recursive O(n)O(1)Using recursion to save time and space.

Another interesting problem related to linked lists is to detect a cycle.

Conclusion 

While this problem looks easy at first glance, it is very difficult to find the solution instantly in a solution. That’s why it is also included in leetcode and other interview question websites as well. But now you know how to merge two sorted linked lists using the recursion, along with its time and space complexities.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.