【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 = 1;
        while(p->next != NULL){n++; p = p->next;}
        return MergeSort(head, n);
    }

    ListNode * MergeSort(ListNode * head, int n)
    {
        if(n == 0)
            return NULL;
        else if(n == 1)
        {
            return head;
        }
        else
        {
            int m = n / 2;
            //下面这种划分的方法很挫 应用后面大神的方法
            ListNode * headb = head; 
            ListNode * p = NULL;
            int k = 1;
            while(k < m + 1)
            {
                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 != 0)
        {
            head = new ListNode(n);
            createList(head->next);
        }
    }
};

int main()
{
    Solution s;
    ListNode * L = NULL;
    s.createList(L);

    ListNode * LS = s.sortList(L);

    return 0;
}

 

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

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;
}