Table of contents

Merge two sorted Linked Lists

Given two singly linked lists that are sorted in ascending order, the task is to merge them into a single sorted linked list.

Input-Output Examples

Example 1:

  • Input:
    • List1: 1 -> 3 -> 5 -> NULL
    • List2: 2 -> 4 -> 6 -> NULL
  • Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Example 2:

  • Input:
    • List1: 1 -> 3 -> 5 -> NULL
    • List2: 2 -> 4 -> 6 -> 8 -> NULL
  • Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 8 -> NULL

Example 3:

  • Input:
    • List1: 1 -> 3 -> 5 -> NULL
    • List2: NULL
  • Output: 1 -> 3 -> 5 -> NULL

Approach:

Technique to be used: Two-pointer technique

To merge two sorted linked lists, we can use a two-pointer technique. We initialize two pointers at the heads of the two lists and iteratively select the smaller element to add to the merged list.

Steps to implement:

  1. Initialize a dummy node to act as the head of the merged list and a current pointer to keep track of the last node in the merged list.
  2. Use two pointers to traverse both lists, comparing the nodes and attaching the smaller node to the current pointer.
  3. Move the pointer of the list from which the node was taken.
  4. Once one list is exhausted, attach the remaining nodes of the other list to the merged list.
  5. Return the merged list starting from the node next to the dummy node.

C++ Program to merge two sorted Linked lists

cpp
#include <iostream>
using namespace std;

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

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;

        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;
        }

        // Attach the remaining nodes
        current->next = (l1 != NULL) ? l1 : l2;

        return dummy.next;
    }
};

// Helper function to print the linked list
void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    // Creating two linked lists: 1 -> 3 -> 5 and 2 -> 4 -> 6
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    Solution sol;
    ListNode* mergedHead = sol.mergeTwoLists(l1, l2);

    // Printing the merged linked list
    cout << "Merged list: ";
    printList(mergedHead);

    return 0;
}

Java Program to merge two sorted Linked lists

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        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;
        }

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

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

    public static void main(String[] args) {
        // Creating two linked lists: 1 -> 3 -> 5 and 2 -> 4 -> 6
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        Solution sol = new Solution();
        ListNode mergedHead = sol.mergeTwoLists(l1, l2);

        // Printing the merged linked list
        System.out.print("Merged list: ");
        printList(mergedHead);
    }
}

Python Program to merge two sorted Linked lists

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        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 = current.next
        
        # Attach the remaining nodes
        current.next = l1 if l1 else l2
        
        return dummy.next

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating two linked lists: 1 -> 3 -> 5 and 2 -> 4 -> 6
l1 = ListNode(1)
l1.next = ListNode(3)
l1.next.next = ListNode(5)

l2 = ListNode(2)
l2.next = ListNode(4)
l2.next.next = ListNode(6)

sol = Solution()
merged_head = sol.mergeTwoLists(l1, l2)

# Printing the merged linked list
print("Merged list:", end=" ")
print_list(merged_head)

Merging two sorted linked lists can be efficiently achieved using the two-pointer technique. This approach ensures a linear time complexity of O(n + m), where n and m are the lengths of the two lists.

DSA

Related Articles