對鏈表進行插入排序

對鏈表進行插入排序。

插入排序算法：

插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。

每次迭代中，插入排序只從輸入數據中移除一個待排序的元素，找到它在序列中適當的位置，并將其插入。

重復直到所有輸入數據插入完為止。

? ?

示例 1：

輸入: 4->2->1->3

輸出: 1->2->3->4

?

到了鏈表，我們發現一個問題，那就是鏈表不能從后往前遍歷，這就很尷尬了。我本來是嘗試找到一個需要移動的節點（即該節點的值比前驅節點的值小），從前往后遍歷，直到找到一個節點值比它大時插入到這個節點前面，然而實現了很久發現代碼又臭又長，關鍵是還總有測試用例不通過，最后還是放棄了。

看了答案發現思路應該是創建一個輔助的新鏈表，并且使用一個指針遍歷原鏈表，每次將原鏈表中的一個節點插入到新鏈表的合適位置（即該節點的值大于新鏈表上的節點的值，又小于后一節點的值）。最后將新鏈表的頭部返回即可。代碼如下，做了詳細的注釋，應該很容易看懂。

1 class ListNode { 2 int val; 3 ListNode next; 4 ListNode(int x) { 5 val = x; 6 } 7 } 8 /** 9 * 鏈表插入排序 10 * */ 11 public ListNode insertionSortList(ListNode head) { 12 //邊界條件判斷 13 if(head==null || head.next == null) 14 return head; 15 16 //創造一個新的鏈表頭部 17 ListNode pre = new ListNode(-1); 18 //用一個臨時變量保存頭節點 19 ListNode ans = pre; 20 //cur是原鏈表上的指針 21 ListNode cur = head; 22 while (cur != null) { 23 //每次循環前重置pre為頭結點，這樣保證每次都從頭往后遍歷 24 pre = ans; 25 26 //當pre.next.val大于cur.val時停止循環 27 while (pre.next != null && pre.next.val < cur.val) { 28 pre = pre.next; 29 } 30 31 //pre.next.val 大于 cur.val，此時應該把cur插入到pre后 32 //保存原鏈表當前節點的下一節點 33 ListNode tmp = cur.next; 34 //把cur插入到pre之后 35 cur.next = pre.next; 36 pre.next = cur; 37 38 //cur指針后移一位 39 cur = tmp; 40 } 41 return ans.next; 42 }

?

?

?

轉載于:https://www.cnblogs.com/kexinxin/p/10195970.html

總結

以上是生活随笔為你收集整理的Leetcode 147.对链表进行排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。