Partitioning a linked list around a given value and keeping the original order | C ++ program to partition a linked list around a given value . ; Link list Node ; A utility function to create a new node ; Function to make two separate lists and return head after concatenating ; Let us initialize first and last nodes of three linked lists 1 ) Linked list of values smaller than x . 2 ) Linked list of values equal to x . 3 ) Linked list of values greater than x . ; Now iterate original list and connect nodes of appropriate linked lists . ; If current node is equal to x , append it to the list of x values ; If current node is less than X , append it to the list of smaller values ; Append to the list of greater values ; Fix end of greater linked list to NULL if this list has some nodes ; If smaller list is empty ; If smaller list is not empty and equal list is empty ; If both smaller and equal list are non - empty ; Function to print linked list ; Driver program to run the case ; Start with the empty list
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; Node * newNode ( int data ) { struct Node * new_node = new Node ; new_node -> data = data ; new_node -> next = NULL ; return new_node ; } struct Node * partition ( struct Node * head , int x ) { struct Node * smallerHead = NULL , * smallerLast = NULL ; struct Node * greaterLast = NULL , * greaterHead = NULL ; struct Node * equalHead = NULL , * equalLast = NULL ; while ( head != NULL ) { if ( head -> data == x ) { if ( equalHead == NULL ) equalHead = equalLast = head ; else { equalLast -> next = head ; equalLast = equalLast -> next ; } } else if ( head -> data < x ) { if ( smallerHead == NULL ) smallerLast = smallerHead = head ; else { smallerLast -> next = head ; smallerLast = head ; } } else { if ( greaterHead == NULL ) greaterLast = greaterHead = head ; else { greaterLast -> next = head ; greaterLast = head ; } } head = head -> next ; } if ( greaterLast != NULL ) greaterLast -> next = NULL ; if ( smallerHead == NULL ) { if ( equalHead == NULL ) return greaterHead ; equalLast -> next = greaterHead ; return equalHead ; } if ( equalHead == NULL ) { smallerLast -> next = greaterHead ; return smallerHead ; } smallerLast -> next = equalHead ; equalLast -> next = greaterHead ; return smallerHead ; } void printList ( struct Node * head ) { struct Node * temp = head ; while ( temp != NULL ) { printf ( " % d ▁ " , temp -> data ) ; temp = temp -> next ; } } int main ( ) { struct Node * head = newNode ( 10 ) ; head -> next = newNode ( 4 ) ; head -> next -> next = newNode ( 5 ) ; head -> next -> next -> next = newNode ( 30 ) ; head -> next -> next -> next -> next = newNode ( 2 ) ; head -> next -> next -> next -> next -> next = newNode ( 50 ) ; int x = 3 ; head = partition ( head , x ) ; printList ( head ) ; return 0 ; }