Linked List: Given Linked list and a value K, partition the list

Problem Statement:

You are given a LL and a value k.

You need to partition the LL such that all the nodes that are less than or equal to K should come first followed by greater value.

Note:

The original relative order of the nodes should be maintained

Examples

Input:

1 -> 2 -> 3 -> 7 -> 6 -> 5 -> 4 -> 9 k = 4

Output:

1 -> 2 -> 3 -> 4 -> 7 -> 6 -> 5 -> 9

Solution Explanation:

Solution is very simple.

As we need to maintain the relative order, for that we need to take 3 different pointers i.e

less_than
euqal_to
greater_than

and add the nodes corresponding to the value of k.

Once all the nodes are processed, then merge all the nodes, getting the solution

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

Code Solution

#include <iostream>
using namespace std;

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

    Node(int val) 
    {
        data = val;
        next = NULL;
    }
};

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

    Node* lessHead = new Node(0); 
    
    Node* equalHead = new Node(0); 
    
    Node* greaterHead = new Node(0);

    Node* less = lessHead;
    Node* equal = equalHead;
    Node* greater = greaterHead;

    Node* curr = head;

    while (curr != NULL) 
    {
        if (curr->data < x) 
        {
            less->next = curr;
            less = less->next;
        } else if (curr->data == x) 
        {
            equal->next = curr;
            equal = equal->next;
        } else 
        {

            greater->next = curr;
            greater = greater->next;
        }
        curr = curr->next;
    }

    greater->next = NULL;  
    
    equal->next = greaterHead->next; 
    
    less->next = equalHead->next;  
    
    Node* newHead = lessHead->next; 

    delete lessHead;
    delete equalHead;
    delete greaterHead;

    return newHead;
}

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


int main() 
{
    // 1 -> 2 -> 3 -> 7 -> 6 -> 5 -> 4 -> 9
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(7);
    head->next->next->next->next = new Node(6);
    head->next->next->next->next->next = new Node(5);
    head->next->next->next->next->next->next = new Node(4);
    head->next->next->next->next->next->next->next = new Node(9);
	
  	int k = 4;

  	cout << "Original List: ";
	display(head);

	head = solution(head, k);

	cout << "\nResult List: ";
	display(head);
    
    return 0;
}

Output

Original List: 1 2 3 7 6 5 4 9

Result List: 1 2 3 4 7 6 5 9