148. Sort List [Merge Sort]

三刷 05/2022

写的很不顺利，没有理解findMid就是要通过把mid prev.next赋值成null,来达到把原来的list从中间分开的目的

另外不知道为啥运行速度这么慢，没找到原因

Time O(nlogn)

Space O(logn) -> the system stack

Runtime: 21 ms, faster than 17.92% of Java online submissions for Sort List.

Memory Usage: 78.5 MB, less than 5.10% of Java online submissions for Sort List.

/**

 * Definition for singly-linked list.

 * 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 sortList(ListNode head) {

        if (head == null || head.next == null) {

            return head;

        }

        ListNode slow = head, fast = head;

        ListNode prev = null;

        while (fast != null && fast.next != null) {

            prev = slow;

            slow = slow.next;

            fast = fast.next.next;

        }

        prev.next = null; // cut the list into two parts, [head, prev] [next, end]

        ListNode left = sortList(head);

        ListNode right = sortList(slow);

        ListNode dummy = new ListNode();

        ListNode pointer = dummy;

       while (left != null && right != null) {

           if (left.val <= right.val) {

               pointer.next = left;

               left = left.next;

           } else {

               pointer.next = right;

               right = right.next;

           }

           pointer = pointer.next;

       }

        ListNode residual = left == null ? right : left;

        while (residual != null) {

            pointer.next = residual;

            residual = residual.next;

            pointer = pointer.next;

        }

        return dummy.next;

    }

}

二刷
78.88 %
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (left != null && right != null) {
            if (left.val > right.val) {
                curr.next = right;
                right = right.next;
            } else {
                curr.next = left;
                left = left.next;
            }
            curr = curr.next;
        }
        curr.next = left == null ? right : left;
        return dummy.next;
       
    } 
}
一刷
public class Solution {
    public ListNode sortList(ListNode head) {
        //base case: null or only one node
        if (head == null || head.next == null) {
            return head;
        }
     
        ListNode mid = findMid(head);
        ListNode midplus = mid.next;
        mid.next = null;
        ListNode leftHead = sortList(head);
        ListNode rightHead = sortList(midplus);
        ListNode newHead = mergeTwo(leftHead, rightHead);
        return newHead;
    }
    private ListNode findMid(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    private ListNode mergeTwo(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = null;
        ListNode curr = null;
        if (l1.val < l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        curr = head;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1 == null) curr.next = l2;
        if (l2 == null) curr.next = l1;
        return head;
    }
 
}