leetcode 148. Sort List

喜欢ヅ旅行 2023-07-10 05:07 9阅读 0赞

[https://leetcode.com/problems/sort-list/][https_leetcode.com_problems_sort-list]

对给定的链表进行排序，要求时间O(nlogn)，空间O(1)。

## 一、问题分析 ##

测试用例：

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)级别的排序有快速排序、堆排序、归并排序，堆排序由于需要O(n)的辅助空间显然不能在这里使用。而归并排序则可以达到时间和空间上的要求，所以下面使用归并排序实现。

## 二、代码实现 ##

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        //递归版本的归并排序
        public ListNode sortList(ListNode head) {
            //递归出口：
            if (head == null || head.next == null) {
                return head;
            }
            
            //子问题：划分两个子链表，分别对其进行归并排序
            ListNode slow = head, fast = head;  //快慢指针，当快指针走到末尾时，慢指针刚好走到中间
            ListNode pre = null;    //两个子链表的分界点（第一个子链表最后一个节点）
            while (fast != null && fast.next != null) {
                pre = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            ListNode second = pre.next;
            pre.next = null;    //切分两个子链表
            head = sortList(head);
            second = sortList(second);
            
            //对两个已经有序的子链表进行合并操作
            return merge(head, second);
        }
        
        //合并链表的操作
        private ListNode merge(ListNode list1, ListNode list2) {
            ListNode tempHead = new ListNode(-1);
            ListNode tempTail = tempHead;
            
            while (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    tempTail.next = list1;
                    list1 = list1.next;
                    tempTail = tempTail.next;
                } else {
                    tempTail.next = list2;
                    list2 = list2.next;
                    tempTail = tempTail.next;
                }
            }
            if (list1 != null) {
                tempTail.next = list1;
            }
            if (list2 != null) {
                tempTail.next = list2;
            }
            
            return tempHead.next;
        }
        
    }

参考：

[https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up(not-recurring)-with-o(1)-space-complextity-and-o(nlgn)-time-complextity][https_leetcode.com_problems_sort-list_discuss_46712_Bottom-to-up_not-recurring_-with-o_1_-space-complextity-and-o_nlgn_-time-complextity]

[https://leetcode.com/problems/sort-list/discuss/46767/Java-solution-with-strict-O(1)-auxiliary-space-complexity][https_leetcode.com_problems_sort-list_discuss_46767_Java-solution-with-strict-O_1_-auxiliary-space-complexity]

[https://leetcode.com/problems/sort-list/discuss/46772/I-have-a-pretty-good-MergeSort-method.-Can-anyone-speed-up-the-run-time-or-reduce-the-memory-usage][https_leetcode.com_problems_sort-list_discuss_46772_I-have-a-pretty-good-MergeSort-method.-Can-anyone-speed-up-the-run-time-or-reduce-the-memory-usage]

[https://leetcode.com/problems/sort-list/discuss/46849/Java-solution-using-merge-sort][https_leetcode.com_problems_sort-list_discuss_46849_Java-solution-using-merge-sort]

[https://leetcode.com/problems/sort-list/discuss/46967/Feeling-confused-about-the-requirement-'constant-memory'][https_leetcode.com_problems_sort-list_discuss_46967_Feeling-confused-about-the-requirement-_constant-memory]

[https_leetcode.com_problems_sort-list]: https://leetcode.com/problems/sort-list/
[https_leetcode.com_problems_sort-list_discuss_46712_Bottom-to-up_not-recurring_-with-o_1_-space-complextity-and-o_nlgn_-time-complextity]: https://leetcode.com/problems/sort-list/discuss/46712/Bottom-to-up%28not-recurring%29-with-o%281%29-space-complextity-and-o%28nlgn%29-time-complextity
[https_leetcode.com_problems_sort-list_discuss_46767_Java-solution-with-strict-O_1_-auxiliary-space-complexity]: https://leetcode.com/problems/sort-list/discuss/46767/Java-solution-with-strict-O%281%29-auxiliary-space-complexity
[https_leetcode.com_problems_sort-list_discuss_46772_I-have-a-pretty-good-MergeSort-method.-Can-anyone-speed-up-the-run-time-or-reduce-the-memory-usage]: https://leetcode.com/problems/sort-list/discuss/46772/I-have-a-pretty-good-MergeSort-method.-Can-anyone-speed-up-the-run-time-or-reduce-the-memory-usage
[https_leetcode.com_problems_sort-list_discuss_46849_Java-solution-using-merge-sort]: https://leetcode.com/problems/sort-list/discuss/46849/Java-solution-using-merge-sort
[https_leetcode.com_problems_sort-list_discuss_46967_Feeling-confused-about-the-requirement-_constant-memory]: https://leetcode.com/problems/sort-list/discuss/46967/Feeling-confused-about-the-requirement-'%20rel=