目錄
- 1.題目
- 2.思路
- 3.代碼實作（Java）
1.題目
給你連結清單的頭結點 head，請将其按升序排列并傳回排序後的連結清單。
進階：你可以在 O(nlogn) 時間複雜度和常數級空間複雜度下，對連結清單進行排序嗎？
示例 1：
輸入：head = [4,2,1,3]
輸出：[1,2,3,4]
示例 2：
輸入：head = [-1,5,3,4,0]
輸出：[-1,0,3,4,5]
示例 3：
輸入：head = []
輸出：[]
提示：
連結清單中節點的數目在範圍 [0, 5 * 104] 内
-105 <= Node.val <= 105
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/sort-list
2.思路
（1）采用LeetCode147.對連結清單進行插入排序的中時間複雜度為O(n2)的插入排序算法，具體步驟可以檢視該文章，此處不再贅述，但是該算法在LeetCode上運作時會顯示超出時間限制的提示！
3.代碼實作（Java）
//（1）思路1
/**
* 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){
return head;
}
//引入preHead:便于在head節點之前插入節點
ListNode preHead=new ListNode(0);
preHead.next=head;
//finalNode:已排序部分的最後一個節點，初始值為head
ListNode finalNode=head;
//目前待排序節點，初始值為head.next
ListNode currNode=head.next;
while(currNode!=null){
if(finalNode.val<=currNode.val){
//已排序部分的最後一個節點值≤目前待排序節點值，finalNode後移一個節點即可
finalNode=finalNode.next;
}else{
//已排序部分的最後一個節點值>目前待排序節點值
//從連結清單頭開始周遊，tmpNode是插入節點currNode位置的前一個節點
ListNode tmpNode=preHead;
while(tmpNode.val<=currNode.val){
tmpNode=tmpNode.next;
}
//将currNode插入到tmpNode之後，具體過程可檢視上面的圖檔
finalNode.next=currNode.next;
currNode.next=tmpNode.next;
tmpNode.next=currNode;
}
//目前待排序節點已完成排序，currNode向後移動一個節點
currNode=finalNode.next;
}
return preHead.next;
}
}