首页 > 代码库 > leetcode - [4]Sort List

leetcode - [4]Sort List

 

Sort a linked list in O(n log n) time using constant space complexity.

思路:采用归并排序或者快速排序

#include <iostream>using namespace std;struct ListNode {    int val;    ListNode *next;    ListNode(int x): val(x), next(NULL) {}};class Solution {public:    ListNode *sortList(ListNode *head) {        if (!head || head->next == NULL) return head;        ListNode *PA = head, *PB = head;                while (PA && PB && PB->next && PB->next->next) {            PA = PA->next;                        PB = PB->next->next;        }        PB = PA->next;        PA->next = NULL;        PA = head;        PA = sortList(PA);            PB = sortList(PB);        return mergeList(PA, PB);    }    ListNode *mergeList(ListNode *PA, ListNode *PB) {        if (!PB) return PA;        if (!PA) return PB;        ListNode *merge, *head;        if (PA->val < PB->val) {            head = PA;            PA = PA->next;        }        else {            head = PB;            PB = PB->next;        }        merge = head;        while (PA && PB) {            if (PA->val < PB->val) {                merge->next = PA;                PA = PA->next;            }            else {                merge->next = PB;                PB = PB->next;            }            merge = merge->next;        }        if (PA) merge->next = PA;        if (PB) merge->next = PB;        return head;    }};int main(int argc ,char *argv[]){    ListNode *p, *q;     p = new ListNode(3);    p->next = new ListNode(2);    p->next->next = new ListNode(4);    Solution *solution = new Solution();    p = solution->sortList(p);    while(p) {        cout << p->val << endl;        p = p->next;    }    return 0;}

 

leetcode - [4]Sort List