LeetCode 148. Sort List

[Woodyiiiiiii]

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

---

这道题要求在O(nlogn)的时间复杂度和常数空间复杂度下完成排序。
显然想到使用归并排序(类似)法。二分完后通过实现两个链表的有序合并完成排序。

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }   
        // divide and conquer
        
        // 1.find middle node
        ListNode mid = head;
        // 注意right不是头节点，是下下一个，保持"2倍"
        // if (right == head) ,错误，会出现栈溢出
        ListNode right = head.next.next;
        ListNode left = head;
        while (right != null && right.next != null) {
            mid = mid.next;
            right = right.next.next;
        }
        
        // 2.divide
        right = mid.next;
        mid.next = null;
        
        // 3.recursive
        left = sortList(left);
        right = sortList(right);
        
        // 4.merge(conquer)
        return merge(left, right);
    }
    private ListNode merge(ListNode l1, ListNode l2) {
        // 按照PDF的设立dummy节点方法
        // eliminate 
        if (l1 == null && l2 == null) {
            return null;
        } 
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode n = dummy;
        ListNode next = null;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                next = l1.next;
                n.next = l1;
                l1.next = null;
                l1 = next;
            }
            else {
                next = l2.next;
                n.next = l2;
                l2.next = null;
                l2 = next;
            }
            n = n.next;
        }
        
        if (l1 != null) {
            n.next = l1;
        }
        if (l2 != null) {
            n.next = l2;
        }
        
        return dummy.next;
        
//         // 按照书上分主副链表进行合并的方法
//         // eliminate 
//         if (l1 == null && l2 == null) {
//             return null;
//         } 
//         if (l1 == null) {
//             return l2;
//         }
//         if (l2 == null) {
//             return l1;
//         }
        
//         // merge
//         // 1.find main and deputy node head
//         ListNode newHead = l1.val <= l2.val ? l1 : l2;
//         ListNode n1 = newHead;
//         ListNode n2 = n1 == l1 ? l2 : l1;
//         // 2.begin
//         while (n1 != null && n2 != null) {
//             // !!!!是n1.next进行判断！！注意逻辑
//             if (n1.next != null && n1.next.val <= n2.val) {
//                 n1 = n1.next;
//             }
//             else {
//                 ListNode next = n2.next;
//                 n2.next = n1.next;
//                 n1.next = n2;
//                 n1 = n2;
//                 n2 = next;
//             }
//         }
//         // n1 != null 不做处理
//         // 注意是if，不是while
//         if (n2 != null) {
//             n1.next = n2;
//         }
        
//         return newHead;
    }
}

分为三个步骤(考点)：1.找到中间节点；2.递归二分链表；3.链表合并排序

---

参考资料:

• https://leetcode.com/problems/sort-list/