Merge two sorted linked lists in java simple and optimal way

Merging two sorted linked lists is a common problem that can be solved efficiently. Here's how you can do it in a simple and optimal way using Java.

Steps:

1. Create a Dummy Node: Use a dummy node to help simplify the merge process. This node will serve as the start of the merged list.
2. Compare Nodes: Compare the current nodes of both linked lists. Attach the smaller node to the merged list and move the pointer of that list forward.
3. Handle Remaining Nodes: If one list is exhausted before the other, attach the remaining nodes of the non-exhausted list to the merged list.
4. Return the Merged List: The merged list starts from the node next to the dummy node.

Java Implementation:

class ListNode {
    int val;
    ListNode next;

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

public class LinkedList {

    // Function to merge two sorted linked lists
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Create a dummy node to act as the starting point
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        // Traverse both lists and compare nodes
        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 exhausted, link the remaining nodes of the other list
        if (l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        // The merged list starts from the next node of the dummy node
        return dummy.next;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create first sorted linked list: 1 -> 3 -> 5
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        // Create second sorted linked list: 2 -> 4 -> 6
        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        System.out.println("First List:");
        list.printList(l1);

        System.out.println("Second List:");
        list.printList(l2);

        // Merge the two lists
        ListNode mergedList = list.mergeTwoLists(l1, l2);

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

Explanation:

1. ListNode Class:

   • Represents each node in the linked list with an integer value (val) and a pointer to the next node (next).

2. mergeTwoLists Method:

   • Dummy Node: A dummy node (dummy) is used to simplify the merging process by providing a starting point.
   • Comparison Loop: We traverse both linked lists, comparing the current nodes. The smaller node is added to the merged list, and we move to the next node in that list.
   • Remaining Nodes: After one of the lists is exhausted, we attach the remaining part of the other list directly to the merged list.
   • Return: Finally, the merged list starts from the node next to the dummy node.

3. printList Method:

   • This utility function prints all the nodes in the linked list for easy visualization.

4. main Method:

   • Create two sorted linked lists: For example, 1 -> 3 -> 5 and 2 -> 4 -> 6.
   • Merge the lists: The merged list will be 1 -> 2 -> 3 -> 4 -> 5 -> 6.
   • Print the lists: Before and after merging to see the effect.

Complexity:

• Time Complexity: ( O(n + m) ), where ( n ) and ( m ) are the lengths of the two linked lists. Each node in both lists is processed exactly once.
• Space Complexity: ( O(1) ), as no additional space is used apart from a few pointers.

This method is both simple and optimal for merging two sorted linked lists, ensuring efficient and clean code.