Linked List: Sort a nearly sorted doubly linked list

Problem Statement:

You are given a DLL with n nodes.

Each node is at-most “k” indices away from its target position.

You need to sort the DLL.

Example:

Input: 3 <-> 2 <-> 1 <-> 5 <-> 4 , k = 2
Output: 1 <-> 2 <-> 3 <-> 4 <-> 5

Solution: Insertion sort

You need to do insertion sort on DLL.

We can use insertion sort, because the nodes are atmost k swaps to away from the required position.

Time Complexity: O(n*k)
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;
        prev = nullptr;
        next = nullptr;
    }
};

Node *solution(Node *head, int k) 
{

    if (head == nullptr || head->next == nullptr)
        return head;

    Node *node = head->next;

    while (node != nullptr) 
    {

        Node *next = node->next;
        Node *curr = node;

        while (curr->prev != nullptr &&
               curr->data < curr->prev->data) 
               {

            Node *node1 = curr->prev->prev; 
            Node *node2 = curr->prev;      
            Node *node3 = curr->next;      
            if (node1 != nullptr)
                node1->next = curr;
            curr->prev = node1;

            node2->next = node3;
            if (node3 != nullptr)
                node3->prev = node2;

            curr->next = node2;
            node2->prev = curr;
        }

        if (curr->prev == nullptr)
            head = curr;

        node = next;
    }
    return head;
}

void print_list(Node *curr) 
{
    while (curr != nullptr) 
    {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

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;

    int k = 2;
    head = solution(head, k);
    print_list(head);

    return 0;
}

Output

1 2 3 4 5