欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
相关标签: List