自己实现LC147题选择排序的问题
来源:5-4 复杂的穿针引线 Swap Nodes in Pairs
软件工程小白菜
2019-06-12
波波老师您好,听了5.4后我自己实现了选择排序,但和在数组中进行选择排序不同:在寻找第i个元素的插入位置时,我没有把i-1,i-2…的元素向后挪动(因为单向链表不支持prev操作),而是从头遍历链表进行寻找,看第一个比第i个元素大的位置在哪里,然后插入在这个位置的前一个即可。虽然通过这种方法也获得了AC,但总感觉怪怪的,感觉我不是在实现选择排序法。请问波波老师这种方法是否也算正确?
谢谢老师!
public ListNode insertionSortList(ListNode head) {
if(head == null)
return null;
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode cur = head;
while(cur.next != null){
if(cur.next.val < cur.val){
ListNode copy = new ListNode(cur.next.val);
ListNode delNode = cur.next;
cur.next = delNode.next;
delNode.next = null;
//System.out.println(copy.val);
ListNode cur2 = dummy;
while(cur2.next != null){
if(cur2.next.val > copy.val){
copy.next = cur2.next;
cur2.next = copy;
//System.out.println(cur2.next.next.val);
break;
}
else{
cur2 = cur2.next;
}
}
}
else{
cur = cur.next;
}
}
return dummy.next;
}
写回答
1回答
-
首先,根据你的函数命名,是插入排序?
我没有细看你的代码,但是你描述的思路是正确的:)由于单向链表不能反向遍历,所以需要每次从头找到插入的正确位置。其实数组也可以每次从头去找插入的位置,有兴趣实现一下看看?:)
至于具体操作,没有办法,链表就是会复杂一些:)
继续加油!:)
112019-06-13
相似问题