Merging two sorted linked lists is a classic computer science problem often asked during technical interviews. The challenge is to combine the two lists into a single, sorted linked list without using any extra space.
How the Algorithm Works
Two Pointers: We'll have two pointers, one for each list.
Compare: At each step, compare the current nodes of both lists and pick the node with the smaller value.
Move Forward: Move the pointer of the list from which the node was chosen to the next node.
Resulting List: The resulting list is constructed by combining the nodes in the required order.
Let's implement the Java program for the same.
Java Program for Merging Two-Sorted Linked Lists
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class SortedListMerger {
public static Node mergeSortedLists(Node l1, Node l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
// Initialize mergedList with a dummy node.
Node dummy = new Node(-1);
Node current = dummy;
while (l1 != null && l2 != null) {
if (l1.data < l2.data) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// If l1 is not exhausted, add remaining nodes of l1.
if (l1 != null) {
current.next = l1;
}
// If l2 is not exhausted, add remaining nodes of l2.
if (l2 != null) {
current.next = l2;
}
return dummy.next; // Return next of dummy to skip the dummy node.
}
public static void main(String[] args) {
Node l1 = new Node(1);
l1.next = new Node(3);
l1.next.next = new Node(5);
Node l2 = new Node(2);
l2.next = new Node(4);
l2.next.next = new Node(6);
Node mergedList = mergeSortedLists(l1, l2);
System.out.println("Merged List:");
while (mergedList != null) {
System.out.print(mergedList.data + " ");
mergedList = mergedList.next;
}
}
}
Output:
Merged List:
1 2 3 4 5 6
Comments
Post a Comment
Leave Comment