溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹java如何實(shí)現(xiàn)對(duì)鏈表進(jìn)行插入排序，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！
對(duì)鏈表進(jìn)行插入排序。
插入排序的動(dòng)畫演示如上。從第一個(gè)元素開始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）。
每次迭代時(shí)，從輸入數(shù)據(jù)中移除一個(gè)元素（用紅色表示），并原地將其插入到已排好序的鏈表中。
插入排序算法：
插入排序是迭代的，每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表。
每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢?，并將其插入?/p>
重復(fù)直到所有輸入數(shù)據(jù)插入完為止。
示例 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}
解析：
關(guān)于排序前面我們介紹了十幾種排序算法，這里讓使用插入排序，其實(shí)插入排序并不難，這里難的是鏈表的斷開和重連。當(dāng)然我們還可以使用其他的方法，比如我們把鏈表的每一個(gè)節(jié)點(diǎn)全部斷開，然后存放到數(shù)組中，接著在排序，最后再把排序好的數(shù)組按順序全部再連接起來即可。
以上是“java如何實(shí)現(xiàn)對(duì)鏈表進(jìn)行插入排序”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼