fork download
copy 
  1. /*
  2. CTCI: 2.4
  3.  
  4. Partition a linked list at value x. ALl the noeds less than x comes before
  5. x and all the nodes more thna x come after
  6. */
  7.  
  8. #include <iostream>
  9. using namespace std;
  10. struct Node
  11. {
  12.     int data;
  13.     Node *next;   
  14. };
  15.  
  16. Node *create_node(int val){
  17.     Node *tmp = new Node();
  18.  
  19.     if (tmp == NULL){
  20.         cout<<"Memeory allocation failed";
  21.         return 0;
  22.     } else {
  23.         tmp->data = val;
  24.         tmp->next = NULL;
  25.         return tmp;
  26.     }
  27. } 
  28.  
  29. void createSLL(Node *& head, int d){
  30.     Node *tmp = create_node(d);
  31.     Node *ptr;
  32.     if (head == NULL)
  33.         head = tmp;
  34.     else{
  35.         ptr = head;
  36.         while(ptr->next != NULL)
  37.             ptr = ptr->next;
  38.         ptr->next = tmp;
  39.     }
  40. }
  41.  
  42. void display(Node *head){
  43.     Node *ptr = head;
  44.     if (ptr == NULL)
  45.         return;
  46.     while(ptr->next != NULL){
  47.         cout<<ptr->data<<"->";
  48.         ptr = ptr->next;
  49.     }
  50.     cout<<ptr->data<<endl;
  51. }
  52.  
  53. Node *pivotPartition(Node * head, int data){
  54.     Node *firsthead = NULL;
  55.     Node *secondhead = NULL;
  56.     Node *tmp = head;
  57.  
  58.     if(tmp == NULL)
  59.         return NULL;
  60.  
  61.     while(tmp != NULL){
  62.         Node *next = tmp->next;
  63.         if(tmp->data < data){
  64.             tmp->next = firsthead;
  65.             firsthead = tmp;
  66.         }
  67.         else{
  68.             tmp->next = secondhead;
  69.             secondhead = tmp;
  70.         }
  71.         tmp = next;
  72.     }
  73.     if(firsthead == NULL)
  74.         return secondhead;
  75.     else
  76.         tmp = firsthead;
  77.     while(tmp->next != NULL)
  78.         tmp = tmp->next;
  79.     tmp->next = secondhead;
  80.     while(firsthead != NULL){
  81.         cout<<firsthead->data;
  82.         firsthead = firsthead->next;
  83.     }
  84.     return firsthead;
  85. }
  86.  
  87. int main(int argc, char const *argv[])
  88. {   Node *head;
  89.     createSLL(head, 3);createSLL(head, 9);createSLL(head, 7);
  90.     createSLL(head, 1);createSLL(head, 4);createSLL(head, 8);
  91.     display(head);
  92.     Node *p = pivotPartition(head, 4);
  93.  
  94.     return 0;
  95. }
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3->9->7->1->4->8
138479
https://ideone.com/SNR0BU
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!