Leetcode 148. 排序链表(归并)

傷城~ 2022-09-14 14:22 184阅读 0赞

## 题目重述 ##

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

#### 进阶： ####

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

#### 示例 1： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Ziz5YWJ5aSn55S35a2pIQ_size_16_color_FFFFFF_t_70_g_se_x_16]

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

#### 示例 2： ####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Ziz5YWJ5aSn55S35a2pIQ_size_20_color_FFFFFF_t_70_g_se_x_16]

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

#### 示例 3： ####

输入：head = []
    输出：[]

#### 提示： ####

链表中节点的数目在范围 [0, 5 * 104] 内
    -105 <= Node.val <= 105

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/sort-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## Java实现 ##

class Solution {
        
        public ListNode sortList(ListNode head) {
        
            if (head == null || head.next == null){
        
                return head;
            }
            // 快慢指针
            ListNode fast = head.next, slow = head;
            while (fast != null && fast.next != null) {
        
                slow = slow.next;
                fast = fast.next.next;
            }
            // 此时慢指针是中点
            ListNode tmp = slow.next;
            slow.next = null;
            // 分别归并排序
            ListNode left = sortList(head);
            ListNode right = sortList(tmp);
            // 辅助ListNode h 作为头部
            ListNode h = new ListNode(0);
            ListNode res = h;
            // 合并链表 
            //比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表
            while (left != null && right != null) {
        
                if (left.val < right.val) {
        
                    h.next = left;
                    left = left.next;
                } else {
        
                    h.next = right;
                    right = right.next;
                }
                h = h.next;
            }
            h.next = left != null ? left : right;
            return res.next;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Ziz5YWJ5aSn55S35a2pIQ_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d6e18ef7805a40e98ed834824ab7ef6c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Ziz5YWJ5aSn55S35a2pIQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9f88878d994b45bb89509c0297ff08f2.png