LeetCode 148: 排序链表

[guodongxiaren]

https://leetcode-cn.com/problems/sort-list

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

[guodongxiaren]

一种写法

?/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode *end = head;//定位到链表的尾部
        while (end->next) {
            end = end->next;
        }
        return mergeSort(head, end);
    }

    // 寻找链表中间节点
    ListNode* findMiddleNode(ListNode* head, ListNode* end) {
        ListNode *slow = head, *fast = head;
        while (fast != end) {
            slow = slow->next;
            fast = fast->next;
            if (fast != end) {
                fast = fast->next;
            }
        }
        return slow;
    }

    // 归并排序
    ListNode* mergeSort(ListNode* head, ListNode *end) {
        if (head == end) {//这段链表只有一个节点
            return head;
        }
        if (head->next == end) {//只有两个节点
            if (head->val > end->val) {
                end->next = head;
                head->next = NULL;
                head = end;
            }
            return head;
        }
        //快慢指针，定位链表中间
        ListNode *slowPtr = findMiddleNode(head, end);

        //第一步  递归，排序右半
        ListNode * rightList = mergeSort(slowPtr->next, end);
        slowPtr->next = NULL;//将左右两部分切开
        //第二步 递归，排序左半
        ListNode * leftList = mergeSort(head, slowPtr);

        //第三步 合并
        ListNode *pHead = new ListNode;
        ListNode *pEnd = pHead;//合并链表的头、尾

        //合并，每次将较小值放入新链表
        while (rightList && leftList) {
            if (rightList->val > leftList->val) {
                pEnd->next = leftList;
                pEnd = pEnd->next;
                leftList = leftList->next;
            } else {
                pEnd->next = rightList;
                pEnd = pEnd->next;
                rightList = rightList->next;
            }
        }
        //可能某个链表有剩余
        if (!rightList) {
            pEnd->next = leftList;
        } else {
            pEnd->next = rightList;
        }
        return pHead->next;
    }
};

注意下面两个代码不等价！为啥呢

        if (head->next == end) {
            if (head->val > end->val) {

        if (head->next == end && head->val > end->val) {

TODO

应该可以复用：合并有序链表的算法。