148. Sort List #

题目 #

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

思路 #

分治，归并排序：寻找链表中心结点，分别对链表前半段和后半段排序，合并排序后的前半段链表和后半段链表

代码 #

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 mergeTwoLists(ListNode headA, ListNode headB) {
        if (headA == null) return headB;
        if (headB == null) return headA;
        
        ListNode sentinel = new ListNode(-1, null);
        ListNode ptr = sentinel;
        
        while (headA != null && headB != null) {
            if (headA.val < headB.val) {
                ptr = ptr.next = headA;
                headA = headA.next;
            }
            else {
                ptr = ptr.next = headB;
                headB = headB.next;
            }
        }
        ptr.next = headA == null ? headB : headA;
        return sentinel.next;
    }
    public ListNode locateMiddle(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode sentinel = new ListNode(-1, head);
        ListNode slow = sentinel, fast = sentinel;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode ptr = locateMiddle(head);
        ListNode headNew = ptr.next;
        ptr.next = null;
        return mergeTwoLists(sortList(head), sortList(headNew));
    }
}

致谢 #

halfrost