148. Sort List

Dear 丶 2022-02-13 16:07 217阅读 0赞

Sort a linked list in O(n log n) time using constant space complexity.
    
    Example 1:
    
    Input: 4->2->1->3
    Output: 1->2->3->4
    Example 2:
    
    Input: -1->5->3->4->0
    Output: -1->0->3->4->5

本题看起来只能用合并排序了。合并排序的思路主要是三步。首先将链表分为两部分；然后对两部分分别排序；最后将两链表合并为一个有序的链表并返回。

public ListNode sortList(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }
            //将链表分割为两部分
            ListNode prev = null, slow = head, fast = head;
            while(fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            prev.next = null;//已将链表分为head和slow两部分
            //分别对两部分都进行排序
            ListNode l1 = sortList(head);
            ListNode l2 = sortList(slow);
            //将两链表合并并返回
            return merge(l1, l2);
        }
    
        //对两链表进行合并
        private ListNode merge(ListNode l1, ListNode l2) {
            ListNode head = new ListNode(0), p = head;
            while(l1 != null && l2 != null) {
                if(l1.val < l2.val) {
                    p.next = l1;
                    l1 = l1.next;
                } else {
                    p.next = l2;
                    l2 = l2.next;
                }
                p = p.next;
            }
            if(l1 == null) {
                p.next = l2;
            }
            if(l2 == null) {
                p.next = l1;
            }
            return head.next;
        }

ListNode定义：

class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
     }