[LintCode] Insertion Sort List

wzyplus 发布于2019-08-14 15:21 / 2676人阅读

摘要：插入排序维基百科一般来说，插入排序都采用在数组上实现。在放这个数之前，这个数的目标位置和原始位置之间的数都要先进行后移。最后，当，即遍历完整个原链表之后，新链表排序完成。

Problem

Sort a linked list using insertion sort.

Example

Given 1->3->2->0->null, return 0->1->2->3->null.

Note

插入排序【维基百科】

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

关于插入排序，我所知道的就是从头部开始，将每个数放到合适的位置。在放这个数之前，这个数的目标位置和原始位置之间的数都要先进行后移。然而这是一个in-place的操作，而对于链表而言，我们只要做一个空链表，然后不断加入原链表中的最小元素即可。
cur是原链表head的指针，不断向后扫描；node是空链表dummy的指针，用node.next与cur所指向的结点进行比较，一旦发现排列好的新链表中有大于cur的结点，就把cur放在node.next，然后进行下一轮循环：cur.next作为原链表新的cur，node返回新链表起点dummy。最后，当cur = null，即遍历完整个原链表之后，新链表排序完成。返回dummy.next即可。

Solution

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode cur = head;
        while (cur != null) {
            ListNode node = dummy;
            while (node.next != null && node.next.val < cur.val) node = node.next;
            ListNode temp = cur.next;
            cur.next = node.next;
            node.next = cur;
            cur = temp;
        }
        return dummy.next;
    }
}

云服务器服务器托管 insertion-sort Insertion LintCode LintCode134_LRU

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65665.html

[LintCode] Kth Largest Element [PriorityQueue]

摘要：可以不要用太简单的方法。先把它装满，再和队列顶端的数字比较，大的就替换掉，小的就。遍历完所有元素之后，顶部的数就是第大的数。 Problem Find K-th largest element in an array. Example In array [9,3,2,4,8], the 3rd largest element is 4.In array [1,2,3,4,5], the...

Hwg 2019-08-14 15:12 评论0 收藏0
Insertion Sort List,Merge Two Sorted Lists,Sort Li

摘要：解题思路题目很简单，就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素，将其插入到前面已经排好序的元素中。但要注意我们要将的前一个节点记录下来在找到中点后，我们要将这样链表才能分割成个。 Insertion Sort ListSort a linked list using insertion sort. 1.解题思路题目很简单，就是要求用插入排序的方法来为链表排...

Brenner 2019-08-16 10:27 评论0 收藏0
147. Insertion Sort List

注意新的list跟原来的list是不相连的，然后把各个状态的点记录好就行： public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; //We started a new list here, not ...

codeGoogle 2019-08-14 14:09 评论0 收藏0
[LintCode] Sort List [分治]

摘要：这道题目可以用分治法来做，首先从链表中点分割链表，然后将两个链表重新排序并合并。 Problem Sort a linked list in O(n log n) time using constant space complexity. Example Given 1-3->2->null, sort it to 1->2->3->null. Note 这道题目可以用分治法来做，首先...

Shisui 2019-08-14 15:32 评论0 收藏0
LintCode547/548_求数组交集不同解法小结

摘要：求数组交集不同解法小结声明文章均为本人技术笔记，转载请注明出处求数组交集要求元素不重复，给出两个数组，求二者交集且元素不重复，查找会超时解法一排序二分查找算法超时主要发生在大数组查找过程，因此采用二分查找提升查找效率，交集用保存实现去重解法 LintCode547/548_求数组交集不同解法小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segme...

gxyz 2019-08-16 10:34 评论0 收藏0