Linked List: Perform bubble sort on Double linked list

Problem Statement:

You are given a double linked list, you need to perform bubble sort on it.

Example:

Input : head: 5<->4<->3<->1<->2
Output : head: 1<->2<->3<->4<->5

Solution 1: Swapping the node values

In this approach, we will traverse the list and comparing the adjacent nodes.

If they are not in sorted order, the data is swapped.

After each pass, the largest element will move to the end of the list.

Will continue till the list is sorted.

Time Complexity: O(n^2)
Space Complexity: O(1)

Solution 2: Changing node link

Instead of swapping the data, in this solution we will re arrange the nodes.

Time Complexity: O(n^2)
Space Complexity: O(1)

Code Solution

#include <iostream>
using namespace std;

class Node 
{
public:
    int data;
    Node* next;
    Node* prev;

    Node(int x) 
    {
        data = x;
        next = NULL;
        prev = NULL;
    }
};


Node* solution_1(Node* head) 
{
    if (head == NULL) return head;

    bool is_swapped;
    Node* curr = NULL;
    Node* last = NULL;

    do 
    {
        is_swapped = false;
        curr = head;

        while (curr->next != last) 
        {
            if (curr->data > curr->next->data) 
            {
              
                int swap_data = curr->data;
                curr->data = curr->next->data;
                curr->next->data = swap_data;

                is_swapped = true;
            }
            curr = curr->next;
        }
        
        last = curr;
    } while (is_swapped);

    return head;
}


Node* solution_2(Node* head) 
{

    if (head == NULL) 
    	return head;

    bool is_swapped;
    Node* curr;
    Node* last = nullptr;

    do 
    {
        is_swapped = false;
        curr = head;

        while (curr->next != last) 
        {
            if (curr->data > curr->next->data) 
            {

                Node* nextNode = curr->next;
                curr->next = nextNode->next;
                nextNode->prev = curr->prev;

                if (curr->next != nullptr) 
                {
                    curr->next->prev = curr;
                }

                if (nextNode->prev != nullptr) 
                {
                    nextNode->prev->next = nextNode;
                } 
                else 
                {
                    head = nextNode;
                }

                nextNode->next = curr;
                curr->prev = nextNode;

                is_swapped = true;
            } 
            else 
            {
                curr = curr->next;
            }
        }

        last = curr;
    } while (is_swapped);

    return head;
}


void print_list(Node* node) 
{
    Node* curr = node;
    while (curr != NULL) 
    {
        cout << " " << curr->data;
        curr = curr->next;
    }
    cout<<"\n";
}

int main() 
{
  
    // 5 <-> 4 <-> 3 <-> 1 <-> 2
    Node* head = new Node(5);
    head->next = new Node(4);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    head->next->next->next = new Node(1);
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = new Node(2);
    head->next->next->next->next->prev
                     = head->next->next->next;

    head = solution_1(head);

    print_list(head);
    head = NULL;
    // 5 <-> 4 <-> 3 <-> 1 <-> 2
    head = new Node(5);
    head->next = new Node(4);
    head->next->prev = head;
    head->next->next = new Node(3);
    head->next->next->prev = head->next;
    head->next->next->next = new Node(1);
    head->next->next->next->prev = head->next->next;
    head->next->next->next->next = new Node(2);
    head->next->next->next->next->prev
                     = head->next->next->next;

    head = solution_2(head);

    print_list(head);

    return 0;
}

Output

 1 2 3 4 5
 1 2 3 4 5