給你鏈表的頭結點 head ，請將其按升序排列并回傳排序后的鏈表，如果能力允許，請保證 O(nlogn) 的時間復雜度和常數級空間復雜度
解題思路
可以借助歸并排序的思想，這樣就能保證時間復雜度為 O(nlogn)，如果使用遞回來實作的話，則不能保證常數級空間復雜度，盡管鏈表的操作不需要額外的存盤空間
通過遞回實作鏈表歸并排序，難點在于如何分割，具體步驟如下
- 使用 fast slow 快慢雙指標法，奇數個節點找到中點，偶數個節點找到中心左邊的節點
- 找到中點 slow 后，執行 slow.next = None 將鏈表切斷
- 繼續遞回分割，輸入當前鏈表左端點 head 和中心節點 slow 的下一個節點 tmp
- 當 head.next == None 時，說明只有一個節點了，直接回傳此節點
/**
* 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.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode tmp = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(tmp);
ListNode p = new ListNode(-1);
ListNode pHead = p;
while(left != null && right != null) {
if(left.val < right.val) {
p.next = left;
left = left.next;
} else {
p.next = right;
right = right.next;
}
p = p.next;
}
p.next = left == null ? right : left;
return pHead.next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/226015.html
標籤：其他
上一篇：當你開始學習編程時，你最希望知道什么？我想起來的只有27件事！
下一篇：蟻劍原理與魔改