-
Notifications
You must be signed in to change notification settings - Fork 0
/
MergeListsInReverseOrder.cpp.txt
130 lines (110 loc) · 2.47 KB
/
MergeListsInReverseOrder.cpp.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/* Given two sorted non-empty linked lists. Merge them in
such a way that the result list will be in reverse
order. Reversing of linked list is not allowed. Also,
extra space should be O(1) */
#include<iostream>
using namespace std;
/* Link list Node */
struct Node
{
int key;
struct Node* next;
};
// Given two non-empty linked lists 'a' and 'b'
Node* SortedMerge(Node *a, Node *b)
{
// If both lists are empty
if (a==NULL && b==NULL) return NULL;
// Initialize head of resultant list
Node *res = NULL;
// Traverse both lists while both of then
// have nodes.
while (a != NULL && b != NULL)
{
// If a's current value is smaller or equal to
// b's current value.
if (a->key <= b->key)
{
// Store next of current Node in first list
Node *temp = a->next;
// Add 'a' at the front of resultant list
a->next = res;
res = a;
// Move ahead in first list
a = temp;
}
// If a's value is greater. Below steps are similar
// to above (Only 'a' is replaced with 'b')
else
{
Node *temp = b->next;
b->next = res;
res = b;
b = temp;
}
}
// If second list reached end, but first list has
// nodes. Add remaining nodes of first list at the
// front of result list
while (a != NULL)
{
Node *temp = a->next;
a->next = res;
res = a;
a = temp;
}
// If first list reached end, but second list has
// node. Add remaining nodes of first list at the
// front of result list
while (b != NULL)
{
Node *temp = b->next;
b->next = res;
res = b;
b = temp;
}
return res;
}
/* Function to print Nodes in a given linked list */
void printList(struct Node *Node)
{
while (Node!=NULL)
{
cout << Node->key << " ";
Node = Node->next;
}
}
/* Utility function to create a new node with
given key */
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
/* Drier program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* res = NULL;
/* Let us create two sorted linked lists to test
the above functions. Created lists shall be
a: 5->10->15
b: 2->3->20 */
Node *a = newNode(5);
a->next = newNode(10);
a->next->next = newNode(15);
Node *b = newNode(2);
b->next = newNode(3);
b->next->next = newNode(20);
cout << "List A before merge: \n";
printList(a);
cout << "\nList B before merge: \n";
printList(b);
/* merge 2 increasing order LLs in descresing order */
res = SortedMerge(a, b);
cout << "\nMerged Linked List is: \n";
printList(res);
return 0;
}