http://oj.leetcode.com/problems/sort-list/

Sort List.cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
typedef ListNode LNode;
class Solution {
public:
    ListNode *sortList(ListNode *head) {
        if (!head || !head->next) return head; // !head->next is necessary to avoid infinite recursion.
        LNode *h1; LNode *h2;
        split(head, h1, h2);
        h1=sortList(h1);
        h2=sortList(h2);
        return merge(h1, h2);
    }
    void split(LNode *head, LNode *&h1, LNode *&h2) { // head shouldn't be NULL.
        h1=head; h2=head->next;
        LNode *p=h1; LNode *q=h2;
        while (p && q) {
            LNode *pre_p=p; LNode *pre_q=q;
            if (p->next) p=p->next->next;
            else p=NULL;
            if (q->next) q=q->next->next;
            else q=NULL;
            pre_p->next=p;
            pre_q->next=q;
        }
        if (p) p->next=NULL;
        if (q) q->next=NULL;
    }
    LNode *merge(LNode *h1, LNode *h2) { // h1, h2 shouldn't be all NULL. return the merged list's head.
        if (!h1) return h2;
        if (!h2) return h1;
        LNode *newHead;
        if (h1->val <= h2->val) { newHead=h1; h1=h1->next; }
        else { newHead=h2; h2=h2->next; }
        newHead->next=NULL; LNode *rear=newHead;
        while (h1 && h2) {
            LNode *cur;
            if (h1->val>h2->val) {
                cur=h2; h2=h2->next;
            } else {
                cur=h1; h1=h1->next;
            }
            rear->next=cur;
            cur->next=NULL;
            rear=cur;
        }
        if (h1) rear->next=h1;
        if (h2) rear->next=h2;
        return newHead;
    }
};

Linked list merge sort.