leetcode 147. Insertion Sort List
程序员文章站
2022-04-06 15:34:30
...
算法分析:
这是一个基于链表的插入排序,同样地设置一个虚拟的头结点vmNode,遍历整个链表时,链表中的每个节点与以vmNode为头节点的链表进行比较,找到插入位置,找到后将该节点插入,最终返回vmNode.next。整个算法的时间复杂度为O(n2),空间复杂度为O(1)。
参考代码:
//leetcode 147. Insertion Sort List
public ListNode insertionSortList(ListNode head) {
ListNode vmNode = new ListNode(0);
ListNode cur = head;
while(cur!=null){
ListNode next = cur.next;
ListNode p=vmNode.next;
ListNode pre = vmNode;
while(p!=null&&p.val<cur.val){
pre = p;
p = p.next;
}
pre.next = cur;
cur.next = p;
cur = next;
}
return vmNode.next;
}