自己实现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回答

liuyubobobo

2019-06-13

首先,根据你的函数命名,是插入排序?


我没有细看你的代码,但是你描述的思路是正确的:)由于单向链表不能反向遍历,所以需要每次从头找到插入的正确位置。其实数组也可以每次从头去找插入的位置,有兴趣实现一下看看?:)


至于具体操作,没有办法,链表就是会复杂一些:)


继续加油!:)

1
1
软件工程小白菜
完了,我写错了,就是插入。感谢老师!
2019-06-13
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程