Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Ans:-
To solve this approach, we will create a Dummy Head. And as the two given list will be sorted, so we have to only compare the individual value of each elements from two different list and will append the lowest one at the end of that dummy head.
Now there can be three scenarios:-
list 1 is blank, then we only add the list 2 at the end of the dummy head as it is as the given lists are already sorted.
Same action will be taken if list 2 is blank, we will just add the list 2 at the end of that dummy head.
And the third logic is, when both the list contains elements then compare the value from each elements of the lists, check the lowest or equal one and add that at the end of that dummy head.
So, for that we have to create a node class, and as we know that one individual node of a list contains a head section, which contains the data and a pointer, which points the next node. And the very first node of a linked list is called head.
So will create one separate class for each of this linked list. The code to create a node class for a linked list is mentioned below:-
class ListNode {
//Data section
int val;
//pointer section
ListNode next;
//constructor default one
ListNode() {}
//constructor that will take only the value of the data at the initialization time
//of that class
ListNode(int val) { this.val = val; }
//constructor that will take only the value of the data and the pointer of
//immediate next node at the initialization time
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
Now, we have to implement the algorithm in the code. So, for that, we will create a separate class with one method, which will implements the solution:-
class Solution {
//Method that will take the two linked list as the input
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//Header node created with some value which is 0 for now
ListNode head = new ListNode(0);
//This header is assigned to a new listNode p
ListNode p=head;
ListNode p1=l1;
ListNode p2=l2;
//If both are not empty
//then compare their values
// and the lowest one is added behind the header
//And the counter is moved to the next node of that list
while(p1!=null && p2!=null){
if(p1.val < p2.val){
p.next = p1;
p1 = p1.next;
}else{
p.next = p2;
p2 = p2.next;
}
p=p.next;
}
//If the first list is empty, then add the
//other list as it is after the dummy header
if(p1==null){
p.next = p2;
}
//If the first list is empty, then add the
//other list as it is after the dummy header
if(p2==null){
p.next = p1;
}
//returned the combined list with out the value of the
//node of the dummy head that was added at th very first
return head.next;
}
}
And now one utility class is created which will print all the element from a given linked list:-
public class SortedList {
//This method will print the each element
// from that linked list
static void printList(ListNode node)
{
while (node != null) {
System.out.printf("%d ", node.val);
node = node.next;
}
}
And at the last, we have created a main method, to run the code:-
public static void main(String[] args) {
// TODO Auto-generated method stub
ListNode head1 = new ListNode(1);
head1.next = new ListNode(3);
head1.next.next = new ListNode(5);
// 1.3.5 LinkedList created
ListNode head2 = new ListNode(0);
head2.next = new ListNode(2);
head2.next.next = new ListNode(4);
Solution k1 = new Solution();
ListNode Final = k1.mergeTwoLists(head1,head2);
printList(Final);
}
But For the LeetCode console, simply add the below mentioned code:-
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//Header node created with some value which is 0 for now
ListNode head = new ListNode(0);
//This header is assigned to a new listNode p
ListNode p=head;
ListNode p1=l1;
ListNode p2=l2;
//If both are not empty
//then compare their values
// and the lowest one is added behind the header
//And the counter is moved to the next node of that list
while(p1!=null && p2!=null){
if(p1.val < p2.val){
p.next = p1;
p1 = p1.next;
}else{
p.next = p2;
p2 = p2.next;
}
p=p.next;
}
if(p1==null){
p.next = p2;
}
if(p2==null){
p.next = p1;
}
return head.next;
}
}Analysis of this above mentioned algorithm:-
Here, we have used only one while loop, which compares the value of each elements from two different linked lists. So, the number of operations simply will depend linearly with the size of each lists. So, the Big O is O(m+n) where m and n is the number of elements present in each node. And space complexity is O(1).