Merge Two Sorted Linked Lists (Easy)
A Singly Linked List sorted in ascending order is passed as an argument. An algorithm that merges the two and returns the head of the Linked List sorted in ascending order as the return value.
There are two Linked Lists as below. When these two Linked Lists are merged while maintaining the sort, they become a single Linked List as shown below. Solution Runtime Complexity O(m + n) Since it uses two pointers to perform a linear scan on two Linked Lists The execution time is O (m + n), where m and n are the lengths of each Linked List.
Space Complexity O(1) The memory is O (1) because it is used for the pointer.
MergeSortList.java
class mergeSortList{
public LinkedListNode merge_sorted(LinkedListNode head1,LinkedListNode head2) {
if (head1 == null) { // edge case
return head2;
} else if (head2 == null) {
return head1;
}
LinkedListNode cur1 = head1; // pointer1
LinkedListNode cur2 = head2; // pointer2
LinkedListNode cur3 = null; // pointer3 for merged list
LinkedListNode head3 = null; // head of merged list
while (cur1 != null && cur1 != null) {
if (head3 == null) {
if (cur1.data < cur2.data) {
head3 = cur1;
cur1 = cur1.next;
} else {
head3 = cur2;
cur2 = cur2.next;
}
cur3 = head3;
} else {
if (cur1.data < cur2.data) {
cur3.next = cur1;
cur1 = cur1.next;
} else {
cur3.next = cur2;
cur2 = cur2.next;
}
cur3 = cur3.next;
}
}
if (cur1 != null) {
cur3.next = cur1;
} else {
cur3.next = cur2;
}
return head3;
}
}
Recommended Posts