Insertion Sort List,Merge Two Sorted Lists,Sort Li

Brenner 发布于2019-08-16 10:27 / 1010人阅读

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

Insertion Sort List
Sort a linked list using insertion sort.

1.解题思路

题目很简单，就是要求用插入排序的方法来为链表排序。插入排序就是每次遍历一个新的元素，将其插入到前面已经排好序的元素中。
因为头结点没法确定，所以我们用一个dummy节点；然后开始向后逐个遍历，当前遍历的节点为cur,另外sortnode每次都指向已经排好序的第一个节点dummy,然后从dummy开始往后，直到找到sortnode.next.val>=cur.val,则表示cur节点要插到有序链表的sortnode后面。

2.代码

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode dummy=new ListNode(0);
        ListNode cur=head;
        while(cur!=null){
            ListNode sortnode=dummy;
            while(sortnode.next!=null&&sortnode.next.val
Merge Two Sorted Lists
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
1.解题思路
合并两个有序链表，同样需要构造一个Dummy节点。
1）考虑特殊情况，如果有一个链表为空，则直接返回另一个链接；
2）利用两个指针p,q遍历两个链表,如果都不为空，则循环继续；
3）使用node指向新链表的最后一个节点，初始化为dummy
4) 比较p,q的数值的大小，如果p小于q,则把p加到node.next,并且node赋值为p,而p指针需要前进一个；
5) 结束循环时，check一下是否还有链表中有剩余元素，并将剩余元素加入到新链表node指针的后面。
2.代码
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode p=l1;
        ListNode q=l2;
        ListNode node=dummy;
        while(p!=null&&q!=null){
            if(p.val
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
1.解题思路
题目要求时间复杂度为O(n log n)，所以我们就想到用归并排序，自然就想到和上一题的mergeTwoLists。
但要做mergeTwoLists，必须得先将当前的list分割成两个List,所以采用递归实现。
要分割链表，最简单的办法就是找到中点，那很明显是利用slow,fast来实现，最后slow就是链表的中间点。但要注意我们要将Slow的前一个节点记录下来pre,在找到中点后，我们要将pre.next=null,这样链表才能分割成2个。
2.代码
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode slow=head,fast=head,pre=null;
        while(fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        ListNode l1=sortList(head);
        ListNode l2=sortList(slow);
        return mergeTwoSortedList(l1,l2);
    }
    private ListNode mergeTwoSortedList(ListNode l1,ListNode l2){
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode dummy=new ListNode(0);
        ListNode p=l1;
        ListNode q=l2;
        ListNode node=dummy;
        while(p!=null&&q!=null){
            if(p.val

云服务器 GPU云服务器 insertion-sort merge_sort merge-sort sort()

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

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

[LintCode] Merge K Sorted Lists [DC/Heap]

摘要：分治做法中，函数依然是将链表结点两两进行比较，然后在函数中迭代两个二分后的结果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...

happyhuangjinjin 2019-08-14 15:32 评论0 收藏0
148. Sort List

摘要：题目分析一看到问题，而且时间复杂度要求又是，很自然地就会想到数组时，如下这道题要求是，所以在上面的基础上还要进行一些额外操作找到的中点，使用快慢指针法。需要注意的是，找到中点后要把链表分成两段，即两个链表。这部分代码应该近似于这道题的答案。 Sort a linked list in O(n log n) time using constant space complexity. 题...

anquan 2019-08-14 17:56 评论0 收藏0
Sorting

摘要：是稳定的排序，但是它需要额外的空间，时间复杂度为程序这个同上也是两个步骤，。最坏情况的时间复杂度为但是在实际情况中，通常是排序的最佳选择。就是有序的完全二叉树，所有我们要先根据已有的数组来建立一个。最后由后往前形成一个有序数组。 Bubble Sort就不说了，下面简单总结一个Selection Sort, Insertion Sort, Merge Sort和Quick Sort: ...

calx 2019-08-14 14:09 评论0 收藏0
[Leetcode] Merge Two Sorted Lists Merge K Sorted L

摘要：注意因为堆中是链表节点，我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见：https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...

stefanieliang 2019-08-14 12:30 评论0 收藏0
【LeetCode Easy】021 Merge Two Sorted Lists

摘要：为减小空间复杂度，最后结果直接修改在上，不重新给分配空间。 Easy 021 Merge Two Sorted Lists Description： Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes o...

icattlecoder 2019-08-16 17:30 评论0 收藏0