148.排序链表

发表于： 2023-09-24 分类于： leetcode

字数： 1166 阅读：≈ 3分钟

🧭 148.排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

思路

基本思想

为了给链表排序，最简单的办法就是将链表转化成数组，之后应用容器自带的排序规则排序，之后再转回链表，就是一个暴力模拟的过程，代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> temp;
        while(head!=nullptr){
            temp.push_back(head->val);
            head=head->next;
        }
        sort(temp.begin(),temp.end());
        ListNode* dummyHead=new ListNode(0);
        ListNode* res=dummyHead;
        for(auto val:temp){
            ListNode* node=new ListNode(val);
            res->next=node;
            res=res->next;
        }
        res->next=nullptr;
        return dummyHead->next;
    }
};

但是这种方法的时间复杂度太高。于是想到了拆分在合并的思想，现将链表拆分成一个一个的单节点，之后将单节点两两合并，这用到了二分法和归并的思想，先使用二分法将链表拆分成一半一半的，一直递归的拆分，当拆分成单节点之后，开始合并

合并的时候是在回溯的时候，每次取左右两个链表依次合并形成更大的链表，之后返回上一层时，形成的链表是一个有序的，这样一层一层向上，最终得到一个完整的排序链表

这种将问题划分的思路称为分治法，将大问题拆分成小问题，当成为单独的问题时就开始向上回溯，在回溯的过程中从小问题的答案组合得到大问题的答案，类似的题目有：

执行流程

递归将当前链表划分成两半（使用快慢指针的思想划分）
当节点是一个单节点时返回
整个链表的节点都变成单节点之后开始回溯
回溯的过程中进行链表的有序合并
形成更大的链表之后向上层返回

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    //暴力法能过
    //递归过不了？？？
    ListNode* sortList(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        ListNode* fast=head->next;
        ListNode* slow=head;
        //将当前链表分割成两半
        while(fast!=nullptr&&fast->next!=nullptr){
            fast=fast->next;
            slow=slow->next;
        }
        ListNode* temp=slow->next;
        //链表等分成两部分
        slow->next=nullptr;
        ListNode* left=sortList(head);
        ListNode* right=sortList(temp);
        ListNode* dummyHead=new ListNode(0);
        ListNode* node=dummyHead;
        //开始合并时说明链表中的额节点被分割成了单个节点
        //每个节点的next都指向了nullptr
        //所以不需要考虑当前链表的尾部是否为空
        //找小的现将当前两个节点合并
        while(left!=nullptr&&right!=nullptr){
            if(left->val<right->val){
                node->next=left;
                node=node->next;
                left=left->next;
            }else{
                node->next=right;
                node=node->next;
                right=right->next;
            }
        }
        //没合并完的节点继续合并，当前子链表合并完成
        node->next=(left==nullptr?right:left);
        return dummyHead->next;

    }
};

java代码为

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public ListNode sortList(ListNode head) {
        //只有一个节点不用划分
        if(head==null||head.next==null)
            return head;
        //重点就在这里，对链表进行划分
        //尝试将当前链表划分成两部分
        ListNode fast=head.next;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //到这里slow走到了链表的正中央，将链表分为两部分
        ListNode temp=slow.next;
        slow.next=null;
        //递归对这两半链表进行排序
        ListNode left=sortList(head);
        ListNode right=sortList(temp);
        ListNode dummtHead=new ListNode(0);
        ListNode node=dummtHead;
        while(left!=null&&right!=null){
            if(left.val<right.val){
                node.next=left;
                left=left.next;
                node=node.next;
            }else{
                node.next=right;
                right=right.next;
                node=node.next;
            }
        }
        //将后面没合并完的链表进行合并
        if(left!=null||right!=null){
            node.next=(left!=null?left:right);
        }else{
            node.next=null;
        }
        return dummtHead.next;
    }
}

总结

利用了归并排序的思想，在递归的过程中对链表拆分，在回溯的过程中对链表合并，最终经过递归回溯，形成了完整的链表，重点就是针对链表的划分，每次将当前链表划分为两部分，然后将两部分继续划分，当划分成只有一个节点时就会回溯，此时就开始合并，从一个节点开始一一合并，然后两两合并，四四合并，八八合并，最终合并成一个有序地链表