Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Given a bidirectional list, write a function that uses merge sort to sort the bidirectional list in increasing order. For example, the double linked list below should be 24810

Merge sort of singly linked lists has been discussed. The important change here is that the preceding pointer is also modified when the two lists are merged.

The following is the implementation of a bidirectional list merge sort.

#include <bits/stdc++.h>
using namespace std;
class Node
{
	public:
	int data;
	Node *next, *prev;
};

Node *split(Node *head);
Copy the code

Merges two linked list functions

Node *merge(Node *first, Node *second)
{
	// If the first list is empty
	if(! first)return second;

	// If the second list is empty
	if(! second)return first;

	// Select a 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;
		returnsecond; }}Copy the code

A function that performs merge sort

Node *mergeSort(Node *head)
{
	if(! head || ! head->next)return head;
	Node *second = split(head);

	// Repeat the left and right parts
	head = mergeSort(head);
	second = mergeSort(second);

	// Merge the sorted halves
	return merge(head,second);
}
Copy the code

Utility function to insert a new node at the beginning of a bidirectional list

void insert(Node **head, int data)
{
	Node *temp = new Node(a); temp->data = data; temp->next = temp->prev =NULL;
	if(! (*head)) (*head) = temp;else{ temp->next = *head; (*head)->prev = temp; (*head) = temp; }}Copy the code

Utility function to print bidirectional linked lists in both forward and backward directions

void print(Node *head)
{
	Node *temp = head;
	cout<<"Forward traversal using the next pointer \n";
	while (head)
	{
		cout << head->data << "";
		temp = head;
		head = head->next;
	}
	cout << "\n traverses backwards with prev pointer \n";
	while (temp)
	{
		cout << temp->data << ""; temp = temp->prev; }}Copy the code

A utility function that swaps two integers

void swap(int *A, int *B)
{
	int temp = *A;
	*A = *B;
	*B = temp;
}
Copy the code

Split a bidirectional linked list (DLL) into two half-sized DLLS

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;
}
Copy the code

The driver

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 << "Sorted linked list \n";
	print(head);
	return 0;
}
Copy the code

Output:

The sorted list is traversed forward using the next pointer3 4 5 10 20 30Use the prev pointer to traverse backwards30 20 10 5 4 3
Copy the code