-
Notifications
You must be signed in to change notification settings - Fork 173
/
Adding code for merging two sorted linked lists.
68 lines (51 loc) · 1.47 KB
/
Adding code for merging two sorted linked lists.
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
/*The linked list node structure is as follows:
template <typename T>
class Node {
public:
T data;
Node* next;
Node(T data) {
next = NULL;
this->data = data;
}
~Node() {
if (next != NULL) {
delete next;
}
}
};
*/
/*The function for merging two sorted linked lists is as:*/
void merge_two_sorted_LL(Node<int>* firstlist, Node<int>* secondlist) {
/*Denoting current node of first linked list by curr1 */
Node* curr1 = firstlist;
Node* next1 = curr1 -> next;
/*Denoting current node of second linked list by curr2 */
Node* curr2 = secondlist;
Node* next2 = curr2 -> next;
while(next1 != NULL && curr2 != NULL) {
if( (curr2 -> data >= curr1 -> data )
&& ( curr2 -> data <= next1 -> data)) {
curr1 -> next = curr2;
curr2 -> next = next1;
curr1 = curr2;
curr2 = next2;
}
else {
}
}
}
Node<int>* returning_final_linkedlist(Node<int>* first, Node<int>* second)
{
if(firstlist == NULL)
return secondlist;
if(secondlist == NULL)
return firstlist;
if(first -> data <= second -> data ){
merge_two_sorted_LL(firstlist, secondlist);
}
else
{
merge_two_sorted_LL(secondlist, firstlist);
}
}