链表排序

目录

插入排序

LeetCode147 对链表进行插入排序

归并排序

LeetCode148 排序链表

---

插入排序

LeetCode147 对链表进行插入排序

/**
 * 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* insertionSortList(ListNode* head) {
        if(head==nullptr) return head;
        if(head->next==nullptr) return head;
        ListNode* first=new ListNode(0);
        first->next=head;
        ListNode* pre=head;
        ListNode* cur=head->next;
        while(cur){
            if(cur->val<pre->val){//当前节点小于最后一个已排序节点
                ListNode* p=first;
                while(cur->val>p->next->val) p=p->next;
                pre->next=cur->next;//保存cur->next

                cur->next=p->next;
                p->next=cur;//在p之后插入cur

                cur=pre->next;//下一个待排序节点
                //此时不用改变pre指向！因为pre没有变，只是待排序元素变了位置
            }
            else{//当前节点大于等于最后一个已排序节点，则不需要插入
                pre=pre->next;
                cur=cur->next;
            }
        }
        return first->next;//不能返回head，head仍然指向原链表的第一个节点
    }
};

 时间复杂度：O(n^2)

空间复杂度：O(1)

归并排序

LeetCode148 排序链表

（1）找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

（2）对两个子链表分别排序。

（3）将两个排序后的子链表合并，得到完整的排序后的链表。

/**
 * 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) {
        return sortL(head,nullptr);
    }
    ListNode* sortL(ListNode* head,ListNode* tail){
        if(head==nullptr) return nullptr;
        if(head->next==tail){ //如果链表只有一个节点
            head->next=nullptr; //将该节点的 next 置为 nullptr，表示这个子链表结束
            return head;
        }
        ListNode* fast=head;
        ListNode* slow=head;
        //使用快慢指针法找到链表的中间点，slow 是中间点，fast 是快指针
        while(fast!=tail){
            fast=fast->next;
            slow=slow->next;
            if(fast!=tail){ //确保fast不越界
                fast=fast->next;
            }
        }
        ListNode* mid=slow; //slow 指向链表的中间节点，作为分割点
        //对链表的左半部分和右半部分分别进行递归排序，然后合并
        return merge(sortL(head,mid),sortL(mid,tail));
    }
    ListNode* merge(ListNode* head1,ListNode* head2){
        ListNode* L=new ListNode(0);
        L->next=nullptr;
        ListNode* r1=head1;
        ListNode* r2=head2;
        ListNode* cur=L;
        while(r1&&r2){
            if(r1->val<r2->val){
                cur->next=r1;
                r1=r1->next;
            }
            else{
                cur->next=r2;
                r2=r2->next;
            }
            cur=cur->next;
        }
        if(r1!=nullptr) cur->next=r1;
        if(r2!=nullptr) cur->next=r2;
        return L->next;
    }
};

 时间复杂度：O(n log n)

空间复杂度：O(log n)