【leetcode】147.(Meduim)Insertion Sort List
解题思路:
设置一个dummy头结点,然后将原链表中的节点一个个拆下来,按升序拼接到新的链表中。
提交代码:
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy=new ListNode(-1);
ListNode cur=dummy;
while(head!=null) {
ListNode pn=head.next;
cur=dummy;
while(cur.next!=null&&cur.next.val<=head.val) {
cur=cur.next;
}
head.next=cur.next;
cur.next=head;
head=pn;
}
return dummy.next;
}
}
运行结果: