DSA-LEARNING-PROGRESS/LL-sort012.cpp at main · Manya0209/DSA-LEARNING-PROGRESS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<iostream>
using namespace std;

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

    Node(int data){
        this -> data= data;
        this -> next= NULL;
        this -> prev= NULL;
    }
    ~Node(){
        int value= this->data;
        if(this->next!=NULL){
            delete next;
            this->next=NULL;
        }
        cout<<"memory is free for data "<<value<<endl;
    }
};

//approach-1

// Node* sortList(Node* head){
//     Node* zeroCount= 0;
//     Node* oneCount= 0;
//     Node* twoCount= 0;

//     Node* temp= head;
//     while(temp!=NULL){
//         if(temp->data==0)
//           zeroCount++;
//         if(temp->data==1)
//           oneCount++;
//         if(temp->data==2)
//           twoCount++;

//         temp= temp->next;
//     }

//     temp= head;
//     while(temp!=NULL){
//         if(zeroCount!=0){
//           temp->data=0;
//           zeroCount--;
//         }
//         if(zeroCount!=0){
//           temp->data=1;
//           oneCount--;
//         }
//         if(twoCount!=0){
//           temp->data=2;
//           twoCount--;
//         }

//         temp= temp->next;
//     }
//     return head;
// }

//approach-2
void insertAtTail(Node* &tail, Node* curr){
    tail->next= curr;
    tail= curr;
}

Node* sortList(Node* head){
    Node* zeroHead= new Node(-1);
    Node* zeroTail= zeroHead;
    Node* oneHead= new Node(-1);
    Node* oneTail= oneHead;
    Node* twoHead= new Node(-1);
    Node* twoTail= twoHead;

    //diffrent lists for 0,1,2

    Node* curr= head;
    while(curr!=NULL){
        int value= curr->data;

        if(value==0)
          insertAtTail(zeroTail, curr);
        if(value==1)
          insertAtTail(oneTail, curr);
        if(value==2)
          insertAtTail(twoTail, curr);
    }
    curr= curr->next;

    //merge list
    if(oneHead->next!=NULL){
        zeroTail->next= oneHead->next;
    }
    else{
        zeroTail->next= twoHead->next;
    }
    oneTail->next= twoHead->next;
    twoTail->next= NULL;

    head= zeroHead->next;

    delete zeroHead;
    delete oneHead;
    delete twoHead;

    return head;
}

int main(){

}