溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹java如何實現對鏈表進行插入排序，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
對鏈表進行插入排序。
插入排序的動畫演示如上。從第一個元素開始，該鏈表可以被認為已經部分排序（用黑色表示）。
每次迭代時，從輸入數據中移除一個元素（用紅色表示），并原地將其插入到已排好序的鏈表中。
插入排序算法：
插入排序是迭代的，每次只移動一個元素，直到所有元素可以形成一個有序的輸出列表。
每次迭代中，插入排序只從輸入數據中移除一個待排序的元素，找到它在序列中適當的位置，并將其插入。
重復直到所有輸入數據插入完為止。
示例 1：
輸入: 4->2->1->3
輸出: 1->2->3->4示例 2：
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5答案：
1public ListNode insertionSortList(ListNode head) {
2 if (head == null)
3 return head;
4 ListNode helper = new ListNode(0);
5 ListNode cur = head;
6 ListNode pre = helper;
7 ListNode next = null;
8 while (cur != null) {
9 next = cur.next;
10 while (pre.next != null && pre.next.val < cur.val) {
11 pre = pre.next;
12 }
13 cur.next = pre.next;
14 pre.next = cur;
15 pre = helper;
16 cur = next;
17 }
18 return helper.next;
19}
解析：
關于排序前面我們介紹了十幾種排序算法，這里讓使用插入排序，其實插入排序并不難，這里難的是鏈表的斷開和重連。當然我們還可以使用其他的方法，比如我們把鏈表的每一個節點全部斷開，然后存放到數組中，接著在排序，最后再把排序好的數組按順序全部再連接起來即可。
以上是“java如何實現對鏈表進行插入排序”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
