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:
- 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.
- 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.
- Handle Remaining Nodes: If one list is exhausted before the other, attach the remaining nodes of the non-exhausted list to the merged list.
- 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:
-
ListNode Class:
- Represents each node in the linked list with an integer value (
val) and a pointer to the next node (next).
- Represents each node in the linked list with an integer value (
-
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.
-
Dummy Node: A dummy node (
-
printList Method:
- This utility function prints all the nodes in the linked list for easy visualization.
-
main Method:
-
Create two sorted linked lists: For example,
1 -> 3 -> 5and2 -> 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.
-
Create two sorted linked lists: For example,
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.
Top comments (0)