Merging Two Sorted Linked Lists using Java

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

Merging two sorted linked lists is a classic computer science problem often asked during technical interviews. The challenge is to combine the two lists into a single, sorted linked list without using any extra space. 

How the Algorithm Works

Two Pointers: We'll have two pointers, one for each list. 

Compare: At each step, compare the current nodes of both lists and pick the node with the smaller value. 

Move Forward: Move the pointer of the list from which the node was chosen to the next node. 

Resulting List: The resulting list is constructed by combining the nodes in the required order. 

Let's implement the Java program for the same. 

Java Program for Merging Two-Sorted Linked Lists 

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SortedListMerger {

    public static Node mergeSortedLists(Node l1, Node l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // Initialize mergedList with a dummy node.
        Node dummy = new Node(-1);
        Node current = dummy;

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

        // If l1 is not exhausted, add remaining nodes of l1.
        if (l1 != null) {
            current.next = l1;
        }

        // If l2 is not exhausted, add remaining nodes of l2.
        if (l2 != null) {
            current.next = l2;
        }

        return dummy.next;  // Return next of dummy to skip the dummy node.
    }

    public static void main(String[] args) {
        Node l1 = new Node(1);
        l1.next = new Node(3);
        l1.next.next = new Node(5);

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

        Node mergedList = mergeSortedLists(l1, l2);

        System.out.println("Merged List:");
        while (mergedList != null) {
            System.out.print(mergedList.data + " ");
            mergedList = mergedList.next;
        }
    }
}

Output:

Merged List:
1 2 3 4 5 6

Explanation: 

We start by defining our linked list's basic structure using the Node class. 

The mergeSortedLists function handles the merging. It starts by checking edge cases - if either of the lists is null. 

The dummy node acts as a placeholder to start building our merged list. This is helpful, so we don't have to handle the special case of initializing the head of the merged list. 

As we iterate over l1 and l2, we determine which node should come next in the merged list based on the current nodes' values in l1 and l2. The current pointer keeps track of the last node in our merged list. 

After processing all elements from either l1 or l2, we might still have some nodes left in one of the original lists. We append these remaining nodes to our merged list. 

In the main method, we test our merging function. The merged list contains elements from both l1 and l2 in sorted order. 

This efficient solution ensures that each node is processed once, making it a linear time O(n) algorithm, where n is the total number of nodes in both linked lists combined.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF