-
Notifications
You must be signed in to change notification settings - Fork 28
/
limca.cpp
132 lines (119 loc) · 2.34 KB
/
limca.cpp
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
131
132
// C++ program for merge sort on doubly linked list
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next, *prev;
};
Node *split(Node *head);
// Function to merge two linked lists
Node *merge(Node *first, Node *second)
{
// If first linked list is empty
if (!first)
return second;
// If second linked list is empty
if (!second)
return first;
// Pick the smaller value
if (first->data < second->data)
{
first->next = merge(first->next,second);
first->next->prev = first;
first->prev = NULL;
return first;
}
else
{
second->next = merge(first,second->next);
second->next->prev = second;
second->prev = NULL;
return second;
}
}
// Function to do merge sort
Node *mergeSort(Node *head)
{
if (!head || !head->next)
return head;
Node *second = split(head);
// Recur for left and right halves
head = mergeSort(head);
second = mergeSort(second);
// Merge the two sorted halves
return merge(head,second);
}
// A utility function to insert a new node at the
// beginning of doubly linked list
void insert(Node **head, int data)
{
Node *temp = new Node();
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else
{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// A utility function to print a doubly linked list in
// both forward and backward directions
void print(Node *head)
{
Node *temp = head;
cout<<"Forward Traversal using next pointer\n";
while (head)
{
cout << head->data << " ";
temp = head;
head = head->next;
}
cout << "\nBackward Traversal using prev pointer\n";
while (temp)
{
cout << temp->data << " ";
temp = temp->prev;
}
}
// Utility function to swap two integers
void swap(int *A, int *B)
{
int temp = *A;
*A = *B;
*B = temp;
}
// Split a doubly linked list (DLL) into 2 DLLs of
// half sizes
Node *split(Node *head)
{
Node *fast = head,*slow = head;
while (fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
Node *temp = slow->next;
slow->next = NULL;
return temp;
}
// Driver program
int main(void)
{
Node *head = NULL;
insert(&head, 5);
insert(&head, 20);
insert(&head, 4);
insert(&head, 3);
insert(&head, 30);
insert(&head, 10);
head = mergeSort(head);
cout << "Linked List after sorting\n";
print(head);
return 0;
}
// This is code is contributed by Anshdeep