leetcode-排序链表

点击：题目链接：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

思路

自定向下，使用快慢指针，不断分治链表然后两两合并。

代码

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return sort(head, nullptr);
    }

    ListNode* sort(ListNode* head, ListNode* tail) {
        if (head == nullptr) return nullptr;

        if (head->next == tail) {
            //若只有两个节点，将其分开
            head->next = nullptr;
            return head;
        }

        ListNode* low = head;
        ListNode* fast = head;

        if (fast->next) fast = fast->next->next;

        while (fast!= tail) {
            low = low->next;
            fast = fast->next;

            if (fast!= tail) {
                fast = fast->next;
            }
        }
        ListNode* mid = low->next;
        return merge(sort(head, mid), sort(mid, tail));
    }
    

    ListNode* merge(ListNode* node1, ListNode* node2) {
        ListNode* head = new ListNode(0);
        ListNode* cur = head;

        while (node1 && node2) {
            ListNode* temp;
            if (node1->val < node2->val) {
                temp = node1->next;
                cur->next = node1;

                cur = node1;
                node1 = temp;
            }
            else{
                temp = node2->next;
                cur->next = node2;

                cur = node2;
                node2 = temp;
            }
        }

        if (!node1) {
            cur->next = node2;
        }
        else if (!node2) {
            cur->next = node1;
        }
        
        return head->next;
    }
};

复杂度

时间：O（NlogN）, 空间：O（logN）

思路二（拓展）

自底向上。 直接两两节点不断比较，再两两合并。

主要注意点一个是择出所需链表节点个数，另一个是在向上合并时要注意成2倍递增

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;

        ListNode* tmplen = head;
        int len = 0;
        while (head) {
            ++len;
            head = head->next;
        }
        
        for (int i = 1; i < len; i<<= 1) {
            ListNode* cur = dummyhead->next;
            ListNode* tail = dummyhead;

            while (cur) {
                ListNode* left = cur;
                ListNode* right = cut(left, i);
                cur = cut(right, i);
                
                ListNode* p = merge(left, right);
                
                tail->next = p;

                while (tail->next) {
                    tail = tail->next;
                }
            }
        }
        return dummyhead->next;

    }

    ListNode* cut(ListNode* head, int n) {
        ListNode* p = head;
        
        if (n == 0) return p;

        while (p) {
            --n;
            if (n > 0) {
                p = p->next;
            }
            else {
                break;
            }
        }

        if (p == nullptr) return nullptr;

        ListNode* tmp = p->next;
        p->next = nullptr;

        return tmp;
    }

    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode* dummyh = new ListNode(0);
        ListNode* cur = dummyh;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                cur = l1;
                l1 = l1->next;
            }
            else {
                cur->next = l2;
                cur = l2;
                l2 = l2->next;
            }
        }

        cur->next = l1 ? l1 : l2;
        
        return dummyh->next;
    }
};

复杂度

时间：O（NlogN）, 空间：O(1)