【leetcode】Sort List (middle)

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

思路：

用归并排序。设输入链表为S，则先将其拆分为前半部分链表A，后半部分链表B。注意，要把A链表的末尾置为NULL。即要把链表划分为两个独立的部分，防止后面错乱。

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

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 == NULL) return NULL;

        ListNode * p = head;

        int n = ;

        while(p->next != NULL){n++; p = p->next;}

        return MergeSort(head, n);

    }

    ListNode * MergeSort(ListNode * head, int n)

    {

        if(n == )

            return NULL;

        else if(n == )

        {

            return head;

        }

        else

        {

            int m = n / ;

            //下面这种划分的方法很挫 应用后面大神的方法

            ListNode * headb = head;

            ListNode * p = NULL;

            int k = ;

            while(k < m + )

            {

                p = headb;

                headb = headb->next;

                k++;

            }

            p->next = NULL;

            ListNode * A = MergeSort(head, m);

            ListNode * B = MergeSort(headb, n - m);

            return Merge(A, B);

        }

    }

    ListNode * Merge(ListNode * A, ListNode * B)

    {

        ListNode * C, * head;

        if(A->val < B->val)

        {

            C = A; A = A->next;

        }

        else

        {

            C = B; B = B->next;

        }

        head = C;

        while(A != NULL && B != NULL)

        {

            if(A->val < B->val)

            {

                C->next = A; A = A->next;

            }

            else

            {

                C->next = B; B = B->next;

            }

            C = C->next;

        }

        if(A != NULL)

        {

            C->next = A;

        }

        else

        {

            C->next = B;

        }

        return head;

    }

    void createList(ListNode * &head)

    {

        int n;

        cin >> n;

        if(n != )

        {

            head = new ListNode(n);

            createList(head->next);

        }

    }

};

int main()

{

    Solution s;

    ListNode * L = NULL;

    s.createList(L);

    ListNode * LS = s.sortList(L);

    return ;

}

大神精简版代码，关键注意划分过程

ListNode *sortList(ListNode *head) {

    if (head == NULL || head->next == NULL)

        return head;

    // find the middle place

    ListNode *p1 = head;

    ListNode *p2 = head->next;

    while(p2 && p2->next) {

        p1 = p1->next;

        p2 = p2->next->next;

    }

    p2 = p1->next;

    p1->next = NULL;

    return mergeList(sortList(head), sortList(p2));

}

ListNode *mergeList(ListNode* pHead1, ListNode* pHead2) {

    if (NULL == pHead1)

        return pHead2;

    else if (NULL == pHead2)

        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->val < pHead2->val)

    {

        pMergedHead = pHead1;

        pMergedHead->next = mergeList(pHead1->next, pHead2);

    }

    else

    {

        pMergedHead = pHead2;

        pMergedHead->next = mergeList(pHead1, pHead2->next);

    }

    return pMergedHead;

}

巴特西

【leetcode】Sort List (middle)

最新文章

热门文章