排序链表

148. 排序链表

难度中等1296

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

进阶：

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

归并排序

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }


    public ListNode mergeSort(ListNode head){
        // 只剩下一个元素时
        if(head==null||head.next==null)return head;
        
        // 快慢指针找到中间节点
        ListNode fast = head;
        ListNode slow = head;

        while(fast!=null){
            fast = fast.next;
            if(fast!=null){
                fast = fast.next;
                // 注意这个判断十分重要，如果没有则会进入死循环
                if(fast!=null)slow = slow.next;
            }
        }
		
        ListNode nex = slow.next;
        // 将链表断开
        slow.next = null;
		// 对链表的前半部分进行归并排序
        ListNode left = mergeSort(head);
        // 对链表的后半部分进行归并排序
        ListNode right = mergeSort(nex);
		
        // 合并两个链表
        ListNode dummyNode = new ListNode(0);
        ListNode pre = dummyNode;
		// 合并公共部分
        while(left!=null&&right!=null){
            if(left.val<=right.val){
                pre.next = left;
                left = left.next;
            }else{
                pre.next = right;
                right = right.next;
            }
            pre = pre.next;
        }
        // 将剩余的部分添加到链表的后面
        if(left!=null) pre.next = left;
        if(right!=null) pre.next = right;

        return dummyNode.next;
    }
}

赏

谢谢你请我吃糖果

微信