目錄
- 1.題目
- 2.思路
- 3.代碼實作（Java）
1.題目
對連結清單進行插入排序。
插入排序的動畫示範如上。從第一個元素開始，該連結清單可以被認為已經部分排序（用黑色表示）。
每次疊代時，從輸入資料中移除一個元素（用紅色表示），并原地将其插入到已排好序的連結清單中。
插入排序算法：
插入排序是疊代的，每次隻移動一個元素，直到所有元素可以形成一個有序的輸出清單。
每次疊代中，插入排序隻從輸入資料中移除一個待排序的元素，找到它在序列中适當的位置，并将其插入。
重複直到所有輸入資料插入完為止。
示例 1：
輸入: 4->2->1->3
輸出: 1->2->3->4
示例 2：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/insertion-sort-list
2.思路
（1）從前往後進行插入排序，具體步驟如下：
（1.1）先判斷連結清單是否為空，如果為空，則直接傳回，否則進行下一步；
（1.2）建立插入排序需要用到的節點：
| 節點名稱 | 作用 |
|---|---|
| preHead | 便于在head節點之前插入節點 |
| finalNode | 已排序部分的最後一個節點，初始值為head |
| currNode | 目前待排序節點，初始值為head.next |
（1.3）從前往後開始周遊連結清單（currNode為null時結束周遊）：
如果已排序部分的最後一個節點值≤目前待排序節點值，則将finalNode後移一個節點即可；
如果已排序部分的最後一個節點值>目前待排序節點值，則從連結清單頭開始周遊，找到插入節點currNode位置的前一個節點tmpNode，并将currNode插入到tmpNode之後，下面的圖檔解釋了對應的三行插入代碼：
由于目前待排序節點已完成排序，是以将currNode向後移動一個節點
（1.4）周遊結束後，傳回preHead.next即可。
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 insertionSortList(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;
}
}