排序链表-蒲公英云

排序链表

题目描述

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

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

解法

思路1，归并排序

public ListNode sortList(ListNode head) { 
    if(head == null || head.next==null) { 
        return head;
    }
    //获取中间节点
    ListNode mid = findMid(head);
    //左右分别递归进行排序
    ListNode right = sortList(mid.next);
    mid.next =null;
    ListNode left = sortList(head);
    //最终进行merge
    return merge(left, right);
}
ListNode merge(ListNode firstNode, ListNode secondNode) { 
    //哑结点
    ListNode head = new ListNode(0);
    ListNode cur = head, first = firstNode, second = secondNode;
    while(first != null && second !=null) { 
        while(first != null && first.val < second.val) { 
            cur.next = first;
            cur = cur.next;
            first = first.next;
        }
        while(first != null && second !=null && first.val >= second.val) { 
            cur.next = second;
            cur = cur.next;
            second = second.next;
        }
    }
    if(first != null) { 
        cur.next = first;
    }else if (second !=null) { 
        cur.next = second;
    }
    return head.next;
}
ListNode findMid(ListNode head) { 
    ListNode slowNode = head, fastNode = head.next;
    while(fastNode != null && fastNode.next!=null) { 
        slowNode = slowNode.next;
        fastNode = fastNode.next.next;
    }
    return slowNode;
}