Merge Two Sorted Linked List

Brute force approach: create a vector for storing the data of both linked list and start iterating both the linked list one by one and storing the data when iterations are completed after that create a new linked list from the stored elements this way we will get the sorted linked list.Time complexity is O(l1+l2)+nlogn+O(l1+l2) and space complexity is O(l1+l2);

Better approach:create a dummy node so that we can keep track the head of final linked list .

start pointing current node to dummy so that we can traverse both the linked list and keep track of where the current node is which will be used throughout the traversal and mainly used for linking both the linked list and when traversal completed return the dummy next which will point the head of merge linked list. TC is O(l1+l2) and SC is O(1);

Node* sortedMerge(Node* head1, Node* head2) { // code here Node* dummy=new Node(0); Node* curr=dummy; while(head1 && head2){ if(head1->data<=head2->data){ curr->next=head1; head1=head1->next; } else{ curr->next=head2; head2=head2->next; } curr=curr->next; } if(head1){ curr->next=head1; } if(head2){ curr->next=head2; } return dummy->next; }