本文共 1275 字，大约阅读时间需要 4 分钟。

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

进阶：

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

归并排序

/** * 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,null);    }    public ListNode mergeSort(ListNode head,ListNode tail){
           // 截止条件        if(head==null){
               return null;        }        if(head.next==tail){
               head.next = null;            return head;        }        // 找mid        // 快慢指针        ListNode slow = head,fast = head;        while(fast!=tail&&fast.next!=tail){
               slow = slow.next;            fast = fast.next.next;        }        ListNode mid = slow;        ListNode left = mergeSort(head,mid);        ListNode right = mergeSort(mid,tail);        ListNode sorted =  merge(left,right);        return sorted;    }    // 合并两个有序链表    public ListNode merge(ListNode head1,ListNode head2){
           ListNode dummy = new ListNode(-1);        ListNode pre = dummy;        while(head1!=null&&head2!=null){
               if(head1.val

转载地址：http://rzwdf.baihongyu.com/