Thể loại
Loại hình
Tin tức

bangnam.com

Relaxed, inspiring essays about happiness.

10.7K

10

8

Merge two sorted linked list without creating any new Node

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we will learn how to Merge two sorted linked list such that the final linked list is also sorted in linear time O(N).

Table of contents:

  1. Problem Statement: Merge two sorted linked lists
  2. Algorithm
  3. Implementation (Step by Step)

Let us get started with Merge two sorted linked lists.

Problem Statement: Merge two sorted linked lists

Merge two given sorted linked list and return head of new linked list which should also be sorted.

Example :

Input: linked list 1 = {1,2,4} , linked list 2 = {1,3,4}
Output: {1,1,2,3,4,4}

Time Complexity :

O(n), beacuse of only one loop iterating only one time.

Algorithm

The steps to Merge two sorted linked lists are:

  • Traverse both Linked Lists linearly from the first node
    • Compare current nodes of both Linked List
    • Delete the smaller node
    • Insert the smaller node at the end of final Linked List
  • If one Linked List is empty during processing, move all elements of the other sorted Linked List to the end of the final Linked List
  • The final Linked List is the merged Linked List.

The implementation steps are:

1.First we define a node by either using struct or class.
2.Create a function to create new nodes.
3.Create a function which takes two sorted linked lists as input and return head of merged linkedlist.
4.Create a function to display the linked list and write main function.

Implementation (Step by Step)

Step 1 : Defining a node

We can do this by either using struct or class.

struct node{ int data; struct node* next; };

or

class node{ public: int data; node* next; };

Step 2 : Function to create a new node

node* newnode(int key) { struct node* temp = new node; temp->data = key; temp->next = NULL; return temp; }

Step 3 : Function to merge sorted linked lists

Approach :

  1. Check if linked list 1 is empty return linked list 2 , or if linked list 2 is empty return linked list 1.

  2. Create new head of the merged linked list by comparing both linked list first elements and choosing the smaller value beacuse we want to maintain the order (should be sorted).

  3. Now, for rest of the elements compare them one by one in a while loop and maintain a new pointer which will keep storing the elements and thus a new sorted linked list will be formed.

  4. In the end just check if any element is left in the linked lists, if yes then add them to the new merged linked list and return head of new linked list.

Working of Code :

Let us take an example :-

Input two linked lists -

List 1 = 1 -> 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = null

Compare first two nodes in both linked lists : [1,1] both are equal we can choose to add any of the two in the final_list and move head pointer of the choosen list, in this case we choose list 1 and move head pointer to next element

List 1 = 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = 1

Compare first two nodes in both linked lists : [2,1] , 1 is smaller so add it to the final_list and move the pointer in list 2.

List 1 = 2 -> 4
List 2 = 3 -> 5
final_list = 1 -> 1

Compare the first two nodes in both linked lists : [2,3], 2 is smaller so add it to the final_list and move the pointer in list 1.

List 1 = 4
List 2 = 3 -> 5
final_list = 1 -> 1 -> 2

Compare the first two nodes in both linked lists : [4,3], 3 is smaller so add it to the final_list and move the pointer in list 2.

List 1 = 4
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3

Compare the last two nodes in both linked lists : [4,5], 4 is smaller so add it to the final_list and move the pointer in list 1.

List 1 = NULL
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3 -> 4

If any one of the two linked lists is pointing to NULL then simply add all the elements of other list in final_list.

final_list = 1 -> 1 -> 2 -> 3 -> 4 -> 5

Note :

We are not deleting the elements of the two linked lists, but as we move the head pointer to the next element in linked list we already lost the previous element because we now don't have any means to go back to previous element, remember in a singly linked list only the address of next element is stored but not the previous one.

Implementation :

//function takes two linked lists as input node* merged_linkedlist(node* head1, node* head2) { //Check if any linked list is empty if (head1 == nullptr) { return head2; } else if (head2 == nullptr) { return head1; } //head pointer for merged linked list node* newhead = nullptr; //check for smallest element by comparing first two elements //of both linked lists if (head1->data <= head2->data) { newhead = head1; //moving head 1 to point to next element in the //linked list 1 for further comparison head1 = head1->next; } else { newhead = head2; //moving head 2 to point to next element in the //linked list 2 for further comparison head2 = head2->next; } //new pointer to move forward and store new elements and //keeping head pointer of new linked list as it is node* temphead = newhead; //run the loop until we reach last element of both lists while (head1 != nullptr && head2 != nullptr) { node* temp = nullptr; if (head1->data <= head2->data) { temp = head1; head1 = head1->next; } else { temp = head2; head2 = head2->next; } //store the next element and move forward to new node temphead->next = temp; temphead = temp; } //if any element is left then add it to final linked list if (head1 != nullptr) { temphead->next = head1; } else if (head2 != nullptr) { temphead->next = head2; } return newhead; }

Step 4 : Main function and Display function

  1. Write a main function to call the merged_linkedlist function.
  2. Wrtie a display function to print merged linked list.
void display(node* node1) { while (node1 != NULL) { printf("%d ", node1->data); node1 = node1->next; } } int main() { //create linked list 1 node* head1 = newnode(1); head1->next = newnode(3); head1->next->next = newnode(5); //print linked list 1 cout<<"linked list 1 - "; display(head1); //create linked list 2 node* head2 = newnode(0); head2->next = newnode(2); head2->next->next = newnode(4); //print linked list 2 cout<<"linked list 2 - "; display(head2); //call merging function node* head = merged_linkedlist(head1, head2); //print merged linked list cout<<"merged linked list - "; display(head); return 0; }

Final Code :

#include<bits/stdc++.h> using namespace std; //defining node type using struct struct node{ int data; struct node* next; }; //function to create new node node* newnode(int key) { struct node* temp = new node; temp->data = key; temp->next =nullptr; return temp; } node* merged_linkedlist(node* head1, node* head2) { //Check if any linked list is empty if (head1 == nullptr) { return head2; } else if (head2 == nullptr) { return head1; } //head pointer for merged linked list node* newhead = nullptr; //check for smallest element by comparing first two elements //of both linked lists if (head1->data <= head2->data) { newhead = head1; //moving head 1 to point to next element in the //linked list 1 for further comparison head1 = head1->next; } else { newhead = head2; //moving head 2 to point to next element in the //linked list 2 for further comparison head2 = head2->next; } //new pointer to move forward and store new elements and //keeping head pointer of new linked list as it is node* temphead = newhead; //run the loop until we reach last element of both lists while (head1 != nullptr && head2 != nullptr) { node* temp = nullptr; if (head1->data <= head2->data) { temp = head1; head1 = head1->next; } else { temp = head2; head2 = head2->next; } //store the next element and move forward to new node temphead->next = temp; temphead = temp; } //if any element is left then add it to final linked list if (head1 != nullptr) { temphead->next = head1; } else if (head2 != nullptr) { temphead->next = head2; } return newhead; } void display(node* node1) { while (node1 != nullptr) { cout<<node1->data<<" "; node1 = node1->next; } cout<<endl; } int main() { //create linked list 1 node* head1 = newnode(1); head1->next = newnode(3); head1->next->next = newnode(5); cout<<"linked list 1 - "; display(head1); //create linked list 2 node* head2 = newnode(0); head2->next = newnode(2); head2->next->next = newnode(4); cout<<"linked list 2 - "; display(head2); node* head = merged_linkedlist(head1, head2); cout<<"merged linked list - "; display(head); return 0; }

Output :

linked list 1 - 1 3 5 linked list 2 - 0 2 4 merged linked list - 0 1 2 3 4 5

With this article at OpenGenus, you must have the complete idea of approaches to Merge two sorted linked lists.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.

Dịch vụ SEO website - Thiết kế Website

★★★★★ 7 đánh giá trên Google
Văn phòng công ty

Địa chỉ: Số 5 Trần Kim Xuyến - P.Trung Hoà - Q.Cầu Giấy - TP. Hả Nội

Điện thoại: 0922 892 892

Trang web: Bangnam.com

Từ Dịch vụ SEO website - Thiết kế Website

"BANGNAM là đơn vị cung cấp Dịch Vụ SEO, Dịch vụ thiết kế Website, Giải pháp quản trị doanh nghiệp ERP hàng đầu tại Việt Nam."

Mọi người cũng tìm kiếm

Thiết kế website Hà Nội
Nhà thiết kế trang web
Thiết kế website bán hàng
Nhà thiết kế trang web
Dịch vụ SEO
Nhà tối ưu công cụ tìm kiếm
Thiết kế website TP HCM
Nhà thiết kế trang web
Thiết kế website Hà Nội
Nhà thiết kế trang web