Merge Two Sorted Linked Lists – Java Program

This Java program demonstrates how to merge two sorted linked lists into a single sorted linked list. The program includes the implementation of the linked list nodes, as well as the merging logic.

Program Structure

The program is structured into three main components:

1. ListNode Class: Defines the node structure for the linked list.
2. MergeSortedLists Class: Contains the method to merge two sorted linked lists.
3. Main Class: Contains the main method to execute the program and test the merge functionality.

Java Code

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public class MergeSortedLists {
        /**
         * Merges two sorted linked lists into one sorted linked list.
         * 
         * @param l1 The head of the first sorted linked list.
         * @param l2 The head of the second sorted linked list.
         * @return The head of the merged sorted linked list.
         */
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            // Create a dummy node to serve as the starting point
            ListNode dummy = new ListNode(0);
            ListNode current = dummy;
            
            // Traverse both lists and merge them
            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 from either list
            if (l1 != null) {
                current.next = l1;
            }
            if (l2 != null) {
                current.next = l2;
            }
            
            // Return the merged list, starting from the next of dummy
            return dummy.next;
        }
    }

    public class Main {
        public static void main(String[] args) {
            // Create two sorted linked lists for testing
            ListNode l1 = new ListNode(1, new ListNode(3, new ListNode(5)));
            ListNode l2 = new ListNode(2, new ListNode(4, new ListNode(6)));
            
            // Merge the lists
            MergeSortedLists merger = new MergeSortedLists();
            ListNode mergedList = merger.mergeTwoLists(l1, l2);
            
            // Print the merged list
            System.out.println("Merged Sorted Linked List:");
            printList(mergedList);
        }
        
        // Helper method to print the linked list
        private static void printList(ListNode head) {
            ListNode current = head;
            while (current != null) {
                System.out.print(current.val + " ");
                current = current.next;
            }
            System.out.println();
        }
    }
    

Explanation

ListNode Class: This class represents a node in the linked list. Each node contains an integer value and a reference to the next node.

MergeSortedLists Class: This class contains the method mergeTwoLists that merges two sorted linked lists. It uses a dummy node to simplify the merging process and ensures that the final merged list is sorted.

Main Class: This class is used for testing the merge functionality. It creates two sample sorted linked lists, merges them using the MergeSortedLists class, and prints the result.