Question

How to merge two sorted linked lists in Java

Answer 1

// Java program that merges two sorted linked lists.

public class MergeSortedLists {

    // Definition of a singly linked list node
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * Merge two sorted linked lists into one sorted list.
     * This method uses a dummy head to simplify pointer handling.
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // Dummy node to start the merged list
        ListNode dummy = new ListNode(0);

        // Tail pointer to build the new list
        ListNode tail = dummy;

        // Traverse both lists while both have nodes
        while (l1 != null && l2 != null) {

            // Pick the smaller value and attach it to the merged list
            if (l1.val < l2.val) {
                tail.next = l1;   // attach l1 node
                l1 = l1.next;     // move l1 forward
            } else {
                tail.next = l2;   // attach l2 node
                l2 = l2.next;     // move l2 forward
            }

            tail = tail.next;     // move the tail forward
        }

        // If one list is not empty, attach the rest
        tail.next = (l1 != null) ? l1 : l2;

        // The merged list starts at dummy.next
        return dummy.next;
    }

    // Build a linked list from an array
    public static ListNode buildList(int[] values) {
        if (values.length == 0) return null;

        ListNode head = new ListNode(values[0]);
        ListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new ListNode(values[i]);
            current = current.next;
        }

        return head;
    }

    // Print a linked list
    public static void printList(ListNode head) {
        ListNode current = head;

        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }

        System.out.println();
    }

    // Main method to demonstrate merging
    public static void main(String[] args) {

        // Create two sorted lists
        ListNode list1 = buildList(new int[]{1, 3, 5, 7});
        ListNode list2 = buildList(new int[]{2, 4, 6, 8});

        System.out.println("List 1:");
        printList(list1);

        System.out.println("List 2:");
        printList(list2);

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

        System.out.println("Merged List:");
        printList(merged);
    }
}



/*
run:

List 1:
1 3 5 7 
List 2:
2 4 6 8 
Merged List:
1 2 3 4 5 6 7 8 

*/

 

70+ SQL courses for beginners and professionals