148. Sort List

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is in the range $[0, 5 * 10^4]$.
• $-10^5 <= Node.val <= 10^5$

Code

Merge sort is defined as a sorting algorithm that works by dividing an array into smaller subarrays, sorting each subarray, and then merging the sorted subarrays back together to form the final sorted array.

class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode middle = getMiddle(head);
        // 3->7->5->1
        // 3->7  5->1
        // 3 7  5 1
        ListNode next = middle.next;
        middle.next = null;
        // 递归调用sortList
        // 直到只剩下一个元素的时候开始merge
        // 然后返回结果
        return merge(sortList(head), sortList(next));
    }

    private ListNode getMiddle(ListNode head){
        ListNode slow = head;
        ListNode fast = head;

        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private ListNode merge(ListNode a, ListNode b){
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        while(a != null && b!=null){
            if(a.val <= b.val){
                cur.next = a;
                a = a.next;
            } else {
                cur.next = b;
                b = b.next;
            }
            cur = cur.next;
        }

        if(a == null) {
            cur.next = b;
        } else {
            cur.next = a;
        }

        return dummy.next;
    }
}