Home » Technical Interview Questions » LinkedList Interview Questions » Merge Two Sorted Lists Leetcode

Merge Two Sorted Lists Leetcode


Reading Time - 7 mins

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

Merge Two Sorted Lists Leetcode

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.

READ  Delete a Node from linked list without head pointer

Space complexity

O(1) we are using a dummy node.

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions