leetcode148-排序链表

class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null)
            return head;
        ListNode new_head=new ListNode(0);
        new_head.next=head;
        ListNode pos=head.next;
        head.next=null; //这里一定要断开指针
        while(pos!=null){
            if(pos.val<=new_head.next.val){
                ListNode tmp=pos.next;
                pos.next=new_head.next;
                new_head.next=pos;
                pos=tmp;
            }else{
                ListNode pre=null;
                ListNode cur=new_head.next;
                while(cur!=null&&cur.val<=pos.val){
                    pre=cur;
                    cur=cur.next;
                }
                ListNode tmp=pos.next;
                pos.next=cur;//cur 一定是大于pos.val的
                pre.next=pos;
                pos=tmp;
            }
        }
        return new_head.next;
    }
}

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;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/sort-list/solution/pai-xu-lian-biao-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。