Table of Contents
What is merge two sorted lists problem on leetcode?
This is so interesting question asked so many times in compnies like Amazon, Oracle, Microsoft, etc. In this problem(Merge Two Sorted Lists Leetcode), we have given two linked lists. Both linked lists are in increasing order. Merge both linked list in such a way that the new merged linked list is in increasing order.
Example
Input
2->4->6
1->3->5->7
Output
1->2->3->4->5->6->7
Explanation
We are given two linked list 2->4->6 and 1->3->5->7 when we merged them and sorted them in increasing order they result to 1->2->3->4->5->6->7.
Approach for Merge Two Sorted Lists Leetcode
We will use a very simple approach. Here we can use the dummy node when the result linked list is empty. The tail pointer of the result linked list always points to the last node in the result linked list.
- We will add nodes from the first linked list or second, linked list such that the result linked list is in increasing order.
- When all elements of one of the linked lists are added in the result linked list then we simply merge the other linked list with the result linked list.
- Now we return the next of the dummy node.
Implementation for Merge Two Sorted Lists Leetcode
C++ code
/* C++ program to merge two sorted linked lists */
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class Node
{
public:
int data;
Node* next;
};
/* pull off the front node of
the source and put it in dest */
void MoveNode(Node** destRef, Node** sourceRef);
Node* SortedMerge(Node* a, Node* b)
{
/* a dummy first node to hang the result on */
Node dummy;
/* tail points to the last result node */
Node* tail = &dummy;
/* so tail->next is the place to
add new nodes to the result. */
dummy.next = NULL;
while (1)
{
if (a == NULL)
{
/* if either list runs out, use the
other list */
tail->next = b;
break;
}
else if (b == NULL)
{
tail->next = a;
break;
}
if (a->data <= b->data)
MoveNode(&(tail->next), &a);
else
MoveNode(&(tail->next), &b);
tail = tail->next;
}
return(dummy.next);
}
/* UTILITY FUNCTIONS */
/* MoveNode() function takes the
node from the front of the source,
and move it to the front of the dest.
It is an error to call this with the
source list empty.
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
Affter calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3} */
void MoveNode(Node** destRef, Node** sourceRef)
{
/* the front source node */
Node* newNode = *sourceRef;
assert(newNode != NULL);
/* Advance the source pointer */
*sourceRef = newNode->next;
/* Link the old dest off the new node */
newNode->next = *destRef;
/* Move dest to point to the new node */
*destRef = newNode;
}
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new Node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(Node *node)
{
while (node!=NULL)
{
cout<<node->data<<" ";
node = node->next;
}
}
/* Driver code*/
int main()
{
/* Start with the empty list */
Node* res = NULL;
Node* a = NULL;
Node* b = NULL;
/* Let us create two sorted linked lists
to test the functions
Created lists, a: 5->10->15, b: 2->3->20 */
push(&a, 15);
push(&a, 10);
push(&a, 5);
push(&b, 20);
push(&b, 3);
push(&b, 2);
/* Remove duplicates from linked list */
res = SortedMerge(a, b);
cout << "Merged Linked List is: \n";
printList(res);
return 0;
}Merged Linked List is: 2 3 5 10 15 20
Java code
/* Java program to merge two
sorted linked lists */
import java.util.*;
/* Link list node */
class Node
{
int data;
Node next;
Node(int d) {data = d;
next = null;}
}
class MergeLists
{
Node head;
/* Method to insert a node at
the end of the linked list */
public void addToTheLast(Node node)
{
if (head == null)
{
head = node;
}
else
{
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
}
/* Method to print linked list */
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver Code
public static void main(String args[])
{
/* Let us create two sorted linked
lists to test the methods
Created lists:
llist1: 5->10->15,
llist2: 2->3->20
*/
MergeLists llist1 = new MergeLists();
MergeLists llist2 = new MergeLists();
// Node head1 = new Node(5);
llist1.addToTheLast(new Node(5));
llist1.addToTheLast(new Node(10));
llist1.addToTheLast(new Node(15));
// Node head2 = new Node(2);
llist2.addToTheLast(new Node(2));
llist2.addToTheLast(new Node(3));
llist2.addToTheLast(new Node(20));
llist1.head = new Gfg().sortedMerge(llist1.head,
llist2.head);
llist1.printList();
}
}
class check
{
Node sortedMerge(Node headA, Node headB)
{
/* a dummy first node to
hang the result on */
Node dummyNode = new Node(0);
/* tail points to the
last result node */
Node tail = dummyNode;
while(true)
{
/* if either list runs out,
use the other list */
if(headA == null)
{
tail.next = headB;
break;
}
if(headB == null)
{
tail.next = headA;
break;
}
/* Compare the data of the two
lists whichever lists' data is
smaller, append it into tail and
advance the head to the next Node
*/
if(headA.data <= headB.data)
{
tail.next = headA;
headA = headA.next;
}
else
{
tail.next = headB;
headB = headB.next;
}
/* Advance the tail */
tail = tail.next;
}
return dummyNode.next;
}
}Merged Linked List is: 2 3 5 10 15 20
Time complexity
O(n+m) where n and m are the lengths of the first and second linked list.
Space complexity
O(1) we are using a dummy node.