插入排序的影片演示如上，從第一個元素開始，該鏈表可以被認為已經部分排序（用黑色表示），每次迭代時，從輸入資料中移除一個元素（用紅色表示），并原地將其插入到已排好序的鏈表中
解題思路
插入排序演算法想必大家都不陌生了，如果不了解的話來看看下面這篇博客吧
用 Java 實作的八種常用排序演算法
難點在于這是個單向鏈表，不能向陣列一樣直接從后往前遍歷，因此我們每找到一個不符合排序規則的元素，都必須從頭再遍歷，找到合適的插入點，而這又考察到有關鏈表的操作
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null) {
return head;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode lastNode = head, curNode = head.next;
while(curNode != null) {
if(lastNode.val <= curNode.val) {
lastNode = lastNode.next;
} else {
ListNode preNode = dummyHead;
while(preNode.next.val <= curNode.val) {
preNode = preNode.next;
}
lastNode.next = curNode.next;
curNode.next = preNode.next;
preNode.next = curNode;
}
curNode = lastNode.next;
}
return dummyHead.next;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/225620.html
標籤：其他