sort_list.cpp

/*
 * leetcode Sort List 
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
#include <iostream>
using namespace std;

 struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
 };
 
 
int cmp(ListNode *a, ListNode *b)
{
    return a->val - b->val;    
}

class Solution {
private:
    /*
     *  using Stack instead of recursion 
     */
    struct Stack {
        struct Element {
            ListNode *info;
            Element *next;
            Element(ListNode *node):info(node){};
        };
        Element *head;
        Element *tail;
        Stack(): head(NULL), tail(NULL) {}
        void Add(ListNode *p) 
        { 
            Element *e = new Element(p);      
            if (head == NULL) {
                head = tail = e; tail->next = NULL; return;
            }
            Element *t = head;
            head = e; e->next = t;
        };
        void pop() 
        {
            if (this->empty()) { return; }
            Element *t = head;
            head = head->next;
            delete t;
            if (head == NULL) { tail = NULL; }
        };
        ListNode *top() 
        {
            if (this->empty()) { return NULL;}
            return head->info;
        };
        bool empty() {
            if (head == NULL) { return true; }
            else { return false; }
        };
        void printStack()
        {
            Element *p = head;
            while (p) {
                p = p->next;
            }
        };
    };
    ListNode *merge(ListNode *l, ListNode *r)
    {
        ListNode *pre, *cur, *h;
        if (l == NULL) { return r; }
        if (r == NULL) { return l; }
        if (cmp(l, r) > 0) { cur = r; r = r->next; }
        else { cur = l; l = l->next; }
        h = pre = cur;
        while (l != NULL && r != NULL) {
            if (cmp(l, r) > 0) { cur = r; r = r->next; } 
            else { cur = l; l = l->next; }
            pre->next = cur; pre = cur;
        }
        if ( l == NULL ) { cur->next = r; }
        else { cur->next = l; }
        return h;
    };
public:
    ListNode *sortList(ListNode *head) {
        int len = 0, nsize = 1;
        Stack s1, s2;
        ListNode *p = head, *pre = head;
        // generate stack;
        while (p) {
            p = p->next; len++;
            pre->next = NULL;
            s1.Add(pre);
            pre = p;
        }
         
        while (nsize < len) {
            s1.printStack();
            while (!s1.empty()) {
                ListNode *p1 = s1.top();
                s1.pop();
                ListNode *p2 = s1.top();
                s1.pop();
                ListNode *newp = this->merge(p1, p2);
                if (newp) { s2.Add(newp); }
            }
            s2.printStack();
            while (!s2.empty()) {
                ListNode *p1 = s2.top();
                s2.pop();
                ListNode *p2 = s2.top();
                s2.pop();
                ListNode *newp = this->merge(p1, p2);
                if (newp) { s1.Add(newp); }
            }
            nsize = nsize << 1;
        }
        head = s1.top();
        s1.pop();
        return head;
    }
};


int main()
{
    ListNode *head = NULL, *cur = NULL;
    int c;
    cin >> c;
    for (int i = 0; i < c; i++) {
        int j;
        cin >> j;
        ListNode *newp = new ListNode(j);
        if (head == NULL) { head = cur = newp; }
        cur->next = newp; cur = newp;
    }

    Solution s;
    head = s.sortList(head);    
    ListNode *p = head, *pre = head;
    while (p) {
        //cout << pre->val << endl;
        p = p->next;
        delete pre;
        pre = p;
    }
    return 0;
}