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.