Given a doubly linked list, write a function to sort the doubly linked list in increasing order using merge sort.
For example, the following doubly linked list should be changed to 2<->4<->8<->10
The important change here is to modify the previous pointers also when merging two lists.
Doubly Linked List:
Doubly Linked List (DLL) is a list of elements and it varies from Linked List. It allows navigation, either forward or backward when compared to Single Linked List. It has two pointers: previous pointer and next pointer. Every element points to next of the list and previous element in list.
Terms used in doubly linked list:
- Link
- Next
- Prev
- Linked list
C Programming to implement of merge sort for doubly linked list:
c
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next, *prev;
};
struct node *split(struct node *head);
struct node *merge(struct node *first, struct node *second)
{
if (!first)
return second;
if (!second)
return first;
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;
}
}
struct node *mergeSort(struct node *head)
{
if (!head || !head->next)
return head;
struct node *second = split(head);
head = mergeSort(head);
second = mergeSort(second);
return merge(head,second);
}
void insert(struct node **head, int data)
{
struct node *temp =
(struct node *)malloc(sizeof(struct node));
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else
{
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
void print(struct node *head)
{
struct node *temp = head;
printf("Forward Traversal using next poitner\n");
while (head)
{
printf("%d ",head->data);
temp = head;
head = head->next;
}
printf("\nBackward Traversal using prev pointer\n");
while (temp)
{
printf("%d ", temp->data);
temp = temp->prev;
}
}
void swap(int *A, int *B)
{
int temp = *A;
*A = *B;
*B = temp;
}
struct node *split(struct node *head)
{
struct node *fast = head,*slow = head;
while (fast->next && fast->next->next)
{
fast = fast->next->next;
slow = slow->next;
}
struct node *temp = slow->next;
slow->next = NULL;
return temp;
}
int main(void)
{
struct node *head = NULL;
insert(&head,5);
insert(&head,20);
insert(&head,4);
insert(&head,3);
insert(&head,30);
insert(&head,10);
head = mergeSort(head);
printf("\n\nLinked List after sorting\n");
print(head);
return 0;
}
Output:
Linked List after sorting
Forward Traversal using next pointer
3 4 5 10 20 30
Backward Traversal using prev pointer
30 20 10 5 4 3
Time Complexity: Time complexity of the above implementation is same as time complexity of MergeSort for arrays. It takes Θ(nLogn) time.
[ad type=”banner”]
