丟人，我就是按插入排序老老實(shí)實(shí)寫的啊。。。。

別人肯定map了hhh。

對(duì)鏈表進(jìn)行插入排序。

插入排序的動(dòng)畫演示如上。從第一個(gè)元素開(kāi)始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）。
每次迭代時(shí)，從輸入數(shù)據(jù)中移除一個(gè)元素（用紅色表示），并原地將其插入到已排好序的鏈表中。

?

插入排序算法：

插入排序是迭代的，每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表。
每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢?#xff0c;并將其插入。
重復(fù)直到所有輸入數(shù)據(jù)插入完為止。
?

示例 1：

輸入: 4->2->1->3
輸出: 1->2->3->4
示例?2：

輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

思路：按插入排序思路寫就可以啦，只是注意鏈表操作，比數(shù)組麻煩很多。

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/ class Solution {public ListNode insertionSortList(ListNode head) {ListNode ans=new ListNode(-1);ListNode temp=null;//要插入的地方ListNode key=null;//要插入的值while(head!=null){key=head;temp=ans;while(temp.next!=null && key.val>temp.next.val){temp=temp.next;}head=head.next;key.next=temp.next;temp.next=key;}return ans.next;} }

?

總結(jié)

以上是生活随笔為你收集整理的leetcode147 对链表进行插入排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。