☆打卡算法☆LeetCode 148. 排序链表 算法解析

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定链表的头结点，返回按照升序排序的链表。”

题目链接：

来源：力扣（LeetCode）

链接： 148. 排序链表 - 力扣（LeetCode）

2、题目描述

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

示例 1：
输入： head = [4,2,1,3]
输出： [1,2,3,4]

示例 2：
输入： head = [-1,5,3,4,0]
输出： [-1,0,3,4,5]

二、解题

1、思路分析

147题是实现链表的插入排序，时间复杂度是O(n²)。

这道题要求时间复杂度更低的排序算法，要求达到O(n log n)的时间复杂度。

可以实现O(n log n)的时间复杂度的排序算法有归并排序、堆排序和快速排序，其中最适合链表的排序算法是归并排序。

首先来了解一下什么是归并排序，归并排序是自顶向下直接合并的方式进行排序，具体过程如下：

• 1、找到链表中点，以中点为界，将链表拆成两个子链表。
• 2、对两个子链表分别排序。
• 3、将两个排序后子链表合并，得到完成链表。

因为上述的过程是通过递归实现的，所以时间复杂度为O(n log n)，空间复杂度为O(log n)。

2、代码实现

代码参考：

class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

3、时间复杂度

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

其中n是链表的长度。

空间复杂度：O(log n)

其中n是链表的长度，空间复杂度主要取决于递归调用的栈空间。

三、总结

通过递归实现链表的归并排序，主要分成两步。

第一步是分割成两个子链表。

可以使用快慢指针，快指针每次移动2步，慢指针每次移动1步，当快指针移动到链表末尾时，慢指针指向链表的节点就是链表的中点。

第二步是子链表递归分别排序。

设置两个指针分别指向两个链表头部，比较两个指针处节点值大小，由小到大加入合并到链表头部，指针交替前进，直到添加完两个链表。