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.

The above is the detailed content of Merge two sorted linked lists in java simple and optimal way. For more information, please follow other related articles on the PHP Chinese website!