Sort a Linked List

Merge Sort a Singly Linked List
http://www.geeksforgeeks.org/merge-sort-for-linked-list/
Merge Sort a Doubly Linked List
http://www.geeksforgeeks.org/merge-sort-for-doubly-linked-list/
Quick Sort a Singly Linked List
http://www.geeksforgeeks.org/quicksort-on-singly-linked-list/
Quick Sort a Doubly Linked List
http://www.geeksforgeeks.org/quicksort-for-linked-list/
Insertion Sort a Singly Linked List
http://quiz.geeksforgeeks.org/insertion-sort-for-singly-linked-list/

Quick Sort for Array and Merge Sort for Linked List ?
http://www.geeksforgeeks.org/why-quick-sort-preferred-for-arrays-and-merge-sort-for-linked-lists/

Question 1:
Sort a linked list that is sorted alternating ascending and descending orders?
Given a Linked List. The Linked List is in alternating ascending and descending orders. Sort the list efficiently.

Example:
Input List:   10->40->53->30->67->12->89->NULL
Output List:  10->12->30->43->53->67->89->NULL
http://www.geeksforgeeks.org/how-to-sort-a-linked-list-that-is-sorted-alternating-ascending-and-descending-orders/

Question 2:
Sort linked list which is already sorted on absolute values
Given a linked list which is sorted based on absolute values. Sort the list based on actual values.

Examples:
Input :  1 -> -10
output: -10 -> 1

Input : 1 -> -2 -> -3 -> 4 -> -5
output: -5 -> -3 -> -2 -> 1 -> 4
http://www.geeksforgeeks.org/sort-linked-list-already-sorted-absolute-values/

Question 3:
Sort a linked list of 0s, 1s and 2s
Given a linked list of 0s, 1s and 2s, sort it.
http://www.geeksforgeeks.org/sort-a-linked-list-of-0s-1s-or-2s/

Question 4:
Given a linked list and the node values range from 1 to 3.It may contain any number of nodes ,sort the list

Strategy:

    Divide the list into 3 different lists,list1 having all 1's, list2 having all 2's and list3 having all 3's.Concatenate list1, list2 and list3

Code:

#include <cstdlib>

#include <cstdio>

using namespace std;

struct Node {

    int data;

    struct Node *next;

    

    Node(int _data):data(_data), next(NULL){}

};

typedef Node *List;

List sort(List l){

    

    List start1 = NULL, start2 = NULL, start3 = NULL;

    

    if(!l)

        return start1;

    

    Node *n1 = NULL, *n2 = NULL, *n3 = NULL;

    

    while(l){

        switch(l->data){

                case 1:

                    if(n1){

                        n1->next = l;

                    } else{

                        start1 = l;

                    }

                    n1 = l;

                       

                    break;

                case 2:

                    if(n2){

                        n2->next = l;

                    } else {

                        start2 = l;

                    }

                    n2 = l;

                    

                        

                    break;

                case 3:

                    if(n3){

                        n3->next = l;

                    }else {

                        start3 = l;

                    }

                    

                    n3 = l;

                        

                    break;

        }

        

        l = l->next;

    }

    

    if(n1)

        n1->next = start2;

    if(n2)

        n2->next = start3;

    if(n3)

        n3->next = NULL;

    

    return start1 ? start1 : start2 ? start2 : start3;

}

List append(List l, int n){

    

    Node *node = new Node(n);

    

    if(!l) return node;

    

    Node *p = l;

    

    while(p->next)

        p = p->next;

    

    p->next = node;

    

    return l;

}

void print(List l) {

    

    while(l){

        printf("%d ", l->data);

        

        l = l->next;

    }

    printf("\n");

}

int main(int argc, char** argv) {

    int n, num;

    

    scanf("%d", &n);

    

    List l = NULL;

    

    for(int i = 0; i < n; ++i){

        scanf("%d", &num);

        l = append(l, num);

    }

    

    print(l);

    

    l = sort(l);

    

    print(l);

    system("pause");

    

    return 0;

}