1. Introduction
In this blog post, we'll delve into a common algorithmic problem in the realm of data structures: merging two sorted linked lists in Java. This problem is a must in programming interviews and is crucial for understanding how to manipulate and merge linked lists.
Problem
Given two sorted linked lists, the goal is to merge them into a single, sorted linked list. The final merged list should also be sorted.
Example:
Input:
1->2->4,
1->3->4
Output:
1->1->2->3->4->4
2. Solution Steps
1. Create a dummy head node to simplify the merging process.
2. Use two pointers, each pointing to the head of the two lists.
3. Compare the node values where the pointers are currently pointing.
4. Append the smaller value to the merged list and move the pointer of that list forward.
5. Continue the process until one of the lists is completely traversed.
6. Append the remaining part of the non-empty list to the merged list.
7. Return the next node of the dummy head as the head of the merged list.
3. Code Program
public class ListNode {
int val; // Value of the node
ListNode next; // Reference to the next node
// Constructor to initialize the node with a value
ListNode(int x) { val = x; }
// Method to print the linked list starting from this node
void printList() {
ListNode temp = this;
while(temp != null) {
System.out.print(temp.val + " "); // Print the value of the current node
temp = temp.next; // Move to the next node
}
System.out.println();
}
}
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummyHead = new ListNode(0); // Dummy head to simplify list manipulation
ListNode current = dummyHead; // Pointer to build the new list
// Iterate as long as both lists have nodes
while (l1 != null && l2 != null) {
if (l1.val < l2.val) { // Compare values of the two nodes
current.next = l1; // Link the smaller node
l1 = l1.next; // Move forward in list l1
} else {
current.next = l2; // Link the smaller node
l2 = l2.next; // Move forward in list l2
}
current = current.next; // Move to the next node in the merged list
}
// Link the remaining part of the list that is not null
current.next = (l1 != null) ? l1 : l2;
return dummyHead.next; // Return the merged list, excluding the dummy head
}
}
// Example usage and testing
public class Main {
public static void main(String[] args) {
ListNode l1 = new ListNode(1); // First node of first list
l1.next = new ListNode(2); // Second node of first list
l1.next.next = new ListNode(4); // Third node of first list
ListNode l2 = new ListNode(1); // First node of second list
l2.next = new ListNode(3); // Second node of second list
l2.next.next = new ListNode(4); // Third node of second list
Solution solution = new Solution();
ListNode mergedList = solution.mergeTwoLists(l1, l2);
mergedList.printList(); // Print the merged list
}
}
Output:
1 1 2 3 4 4
Explanation:
The input lists are 1->2->4 and 1->3->4.
The mergeTwoLists method merges these two lists by comparing the nodes of each list and appending the smaller node to the merged list.
The process continues until all nodes in both lists are merged, resulting in the sorted output 1->1->2->3->4->4.
Comments
Post a Comment
Leave Comment