本文共 1450 字，大约阅读时间需要 4 分钟。

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* findMiddle(ListNode* head){        ListNode* chaser = head;        ListNode* runner = head->next;        while(runner != NULL && runner->next != NULL){            chaser = chaser->next;            runner = runner->next->next;        }        return chaser;    } ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {        if(l1 == NULL){            return l2;        }        if(l2 == NULL){            return l1;        }        ListNode* dummy = new ListNode(0);        ListNode* head = dummy;        while(l1 != NULL && l2 != NULL){            if(l1->val > l2->val){                head->next = l2;                l2 = l2->next;            }            else{                head->next = l1;                l1 = l1->next;            }            head = head->next;        }        if(l1 == NULL){            head ->next = l2;        }        if(l2 == NULL){            head->next = l1;        }        return dummy->next;    }    ListNode* sortList(ListNode* head) {        if(head == NULL || head ->next == NULL){            return head;        }        ListNode* middle = findMiddle(head);        ListNode* right = sortList(middle->next);        middle -> next = NULL;        ListNode* left = sortList(head);        return mergeTwoLists(left, right);    }};

转载地址：http://bytmi.baihongyu.com/