Homework SourseWrite a function to merge two doubly linked lists The input
Solution
The algorithm for LinkedList MergeSort is as follows.
The trick in this algorithm is to use a local list to store the value which is pointing to the actual list to be returned as a result of the function
Step1: START
Step2: GET inputs of list1 and list2
Step3: INITIALIZE mergelist
STEP4: SET mylist = mergelist
Step5: WHILE list1 OR list2 is EMPTY
DO
IF (list1 AND list2) are NOT EMPTY
IF list1.value > list2.value
mylist.next = list2
ELSE
mylist.next = list1
ELSE IF list1 is EMPTY
mylist.next = list2
ELSE
mylist.next = list1
Step6: RETURN mergelist
Step7: STOP
Sample program for the same implemented in C++
//============================================================================
// Name : DoublyLinkedList.cpp
// Author : Kaju
// Version : 0.1
// Copyright : This is just an example code
// Description : MergeSort in C++, Ansi-style
//============================================================================
/*
* C++ Program to Implement Doubly Linked List
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
/*
* Node Declaration
*/
using namespace std;
// struct declaration for node which will hold the integer data with links to previous data and next data
struct node
{
int data;
struct node *next;
struct node *prev;
};
/*
Class Declaration
*/
class DoublyLinkedList
{
private:
struct node *start; // collection of all the nodes
public:
void create(int value);
int peek();
int delete_head();
void display();
int count();
void mergeSort(DoublyLinkedList list1, DoublyLinkedList list2);
DoublyLinkedList()
{
start = NULL;
}
};
/*
* Add data into the list
*/
void DoublyLinkedList::create(int value)
{
struct node *s, *temp;
temp = new(struct node);
temp->data = value;
temp->next = NULL;
if (start == NULL)
{
temp->prev = NULL;
start = temp;
}
else
{
s = start;
while (s->next != NULL)
s = s->next;
s->next = temp;
temp->prev = s;
}
}
/*
* Deletion of the first element from the list
* store the first element in a temp node and then remove it from start.
*/
int DoublyLinkedList::delete_head()
{
struct node *tmp, *q;
int value;
tmp = start;
if(start->next!=NULL)
{
start = start->next;
start->prev = NULL;
}
else
start = NULL;
value = tmp->data;
free(tmp);
return value;
}
/*
* return the first element of Doubly Link List
*/
int DoublyLinkedList::peek()
{
struct node *q;
if (start == NULL)
{
cout<<\"List is empty\"<<endl;
return NULL;
}
else
{
q = start;
return q->data;
}
}
/*
* Display elements of Doubly Link List
*/
void DoublyLinkedList::display()
{
struct node *q;
if (start == NULL)
{
cout<<\"List is empty\"<<endl;
return;
}
q = start;
cout<<\"[\";
while (q != NULL)
{
cout<<q->data;
q = q->next;
if(q != NULL)
{
cout<<\", \";
}
}
cout<<\"]\"<<endl;
}
/*
* Number of elements in Doubly Link List
*/
int DoublyLinkedList::count()
{
struct node *q = start;
int cnt = 0;
while (q != NULL)
{
q = q->next;
cnt++;
}
return cnt;
}
/*
* MergeSort - takes two input lists and then based on the integer data value sorts them in ascending order.
* Adds each data removed from the input lists into the new list.
*/
void DoublyLinkedList::mergeSort(DoublyLinkedList list1, DoublyLinkedList list2)
{
while(list1.count() > 0 || list2.count() > 0) // Checks whether any of the list is empty
{
if(list1.count() > 0 && list2.count() > 0) // checks if both the lists have data
{
if(list1.peek() > list2.peek()) // compares the first element of both the lists
create(list2.delete_head()); // if the second list has greater value then it is removed from the second list and added to the new list
else
create(list1.delete_head());// if the first list has greater value then it is removed from the first list and added to the new list
}
else if(list1.count() == 0) // incase where list one is empty and only list two has value
{
create(list2.delete_head()); // if the second list has value then it is removed from the second list and added to the new list
}
else
{
create(list1.delete_head()); // if the first list has value then it is removed from the first list and added to the new list
}
}
}
int main()
{
DoublyLinkedList firstList;
firstList.create(4);
firstList.create(10);
firstList.create(45);
firstList.create(53);
firstList.create(250);
firstList.create(1020);
cout<<\"List 1: \";
firstList.display();
DoublyLinkedList secondList;
secondList.create(1);
secondList.create(36);
secondList.create(68);
secondList.create(73);
secondList.create(1019);
cout<<\"List 2: \";
secondList.display();
DoublyLinkedList mergedList;
mergedList.mergeSort(firstList, secondList);
cout<<\"Merged List: \";
mergedList.display();
return 0;
}
OUTPUT:
List 1: [4, 10, 45, 53, 250, 1020]
List 2: [1, 36, 78, 673, 1019]
Merged List: [1, 4, 10, 36, 45, 53, 78, 250, 673, 1019, 1020]
