专栏首页架构说每日一题2-对链表进行插入排序

每日一题2-对链表进行插入排序

147. 对链表进行插入排序

  对链表进行插入排序

示例 1:

输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->5

分析

保障正确性-o(n2) ,类似链表翻转,后面数据插入到前面

i

文字描述:

  1. 遍历链表,第一个元素默认是有序的
  2. 在遍历过程中 记录, 有序链表 开始位置: 是否固定下来

head是否改变2个方式

  1. 在遍历过程中 记录, 结束位置 : 如果有序,怎么办 ? 如果无顺序怎么办? 约束条件是什么?
  2. 寻找插入位置

注释code1

/**
 * https://www.lintcode.com/problem/insertion-sort-list/
 *
 *  **/

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @return: The head of linked list.
     */
    ListNode * insertionSortList(ListNode * head) {
        //插入排序
        if(head ==NULL ||head->next ==NULL)
        {   
            //少于一个节点不需要排序
           return head ;
        }
        //01 构造带头节点的单链表,默认第一个节点有序

        ListNode start(0);//保持头节点不变是为了插入方面,也可以不要,每次寻找pre节点时候 判断一下是否null
        start.next=head;

        ListNode* end=head; //有序链表结束位置,end也是遍历的迭代器  
        ListNode* pre=NULL;//辅助变量  
        ListNode* temp=NULL;//辅助变量  
        /** 初始状态
         *   input:7--6--5--4--3 -2 -1 
         *   
         *  start.next---7--6--5--4--3 -2 -1 
         *      |        |  |             
         *      |        |  temp
         *      |        end
         *      Pre
         */

        //遍历剩余 未排序的
        while(end)
        {
            temp=end->next;

            if(end->next ==NULL ||temp->val>end->val)
            {
               end=end->next;
          /** 最后一个元素
         *   input:7--6--5--4--3 -2 -1 
         *   
         *  start.next---1-2--3--4--5 -6 -7----NUll
         *                                |       |             
         *                                |       temp 
         *                                end(end没有改变过一次,end=null 结束循环)
         *      
         */
            }else

        /** 第一次排序
         *   input:7--6--5--4--3 -2 -1 
         *   
         *   before:
         *   start.next---7--6--5--4--3 -2 -1 
         *      |        |  |             
         *      |        |  temp
         *      |        end
         *      Pre
         * 
         * after:
         * start.next---6----7---5--4--3 -2 -1 
         *      |       |    |              
         *      |       |    |  
         *      |       temp end
         *      Pre
         * 
         */ 
         {
               pre=&start;
              while(pre->next &&pre->next->val < temp->val)
              {
                pre=pre->next;//pre插入位置前一个元素  pre->7

              }
              //插入元素 pre -6-7-5

              end->next=temp->next; //7---5
              temp->next=pre->next;//6---7
              pre->next=temp;//start

        }
      }
        return start.next;

    }
};

注释code2

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
         //基本合法检查,还不涉及排序过程
        if(head == NULL || head->next == NULL) {
            return head;
        }

        //01 依赖空间 
        ListNode first(0); //有序链表头开始部分,固定头节点位置,保证插入节点元素 pre节点一定存在。
        first.next=head; //第一默认有序  head->6->5->1->8
        ListNode* cur = head; // 有序链表头结束部分

        ListNode* pre = NULL;//插入排序需要插入记录位置,每次都需要重新计算

        //从第一个元素开始遍历链表,假设第一个元素是有序的
        while(cur) {
            //满足条件 1-8
            if(cur->next &&cur->next->val <cur->val)
            {
             //寻找插入位置  .
             pre=&first;//从有序链表head开始遍历.次数,pre 指向head节点,没有数据
             while(cur->next&&pre->next && cur->next->val>pre->next->val) // head->6->5->1->8
             {
                pre=pre->next;//pre->next 就是插入地方。pre是前面一个节点。存在插入规则,是在固定节点后面插入
             }
          // pre  <temp < pre-next

            //插入过程 类似节点翻转最前面位置(pre->next 就是插入地方)
            ListNode* temp = cur->next; //记录待插入元素5,head->6->5->1
            cur->next=temp->next; //移除待插入元素5 ,移动下一个元素 head->6->1
            temp->next =pre->next;//待插入元素5后面节点。 
                                  //                    5  ->6->1    
                                  //                   head->6->1 

            pre->next=temp;//待插入元素5前面节点。 head->5->6->1
            //这里不需要一定cur=cur->next,移动下一个元素 head->6->1 完成
            }else
            {
                 cur=cur->next;//移动下一个元素
            }             
        }

        return first.next;
    }

};

总结

链表这样结构 必须定义 固定开始节点和结束节点 这样方面插入

本文分享自微信公众号 - 架构说(JiaGouS),作者:程序员小王

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 题目:将链表的奇数位和偶数位调换组成新的链表

    题目:将链表的奇数位和偶数位调换组成新的链表 原题链接: http://oj.leetcode.com/problems/swap-nodes-in-pairs...

    程序员小王
  • memcache启动过程以及线程模型

    耗时三天 阅读了 2个文件 memcached-1.5.4\memcached.c memcached-1.5.4\thread.c 具体过程已经记不清楚了,可...

    程序员小王
  • 递归回溯--复原IP地址

    There is no coming to consciousness without pain.

    程序员小王
  • [PHP] 算法-复制复杂链表的PHP实现

    陶士涵
  • 如何指定Spark1作业中Driver和Executor使用指定范围内端口

    在CDH集群中提交Spark作业,大家也都知道Spark的Driver和Executor之间通讯端口是随机的,Spark会随选择1024和65535(含)之间的...

    Fayson
  • [Leetcode][python]删除排序链表中的重复元素/删除排序链表中的重复元素 II

    如果当前节点有后一个节点,且它们的值相等,那么当前节点指向后一个节点的下一个节点,这样就可以去掉重复的节点。

    后端技术漫谈
  • C语言自定义函数如何返回数组(上)?

    最近看到一些同学问题,有提到说:如何在一个函数中返回数组呢? 能否直接在自定义 函数中,写成char *类型返回值,直接返回呢?,代码如下: ? 直接返回str...

    编程范 源代码公司
  • 「递归」第3集 | 向善的信念,让技术自带光芒

    ? 我们为什么叫「递归」 “递归” (recursion) 是一种在程序设计语言中被广泛使用的算法。它有两大特点,一是调用自己,二是化繁为简。我们当中那些优...

    腾讯技术工程官方号
  • 作为程序员,你必须了解这些关于计算机的知识

    我是攻城师
  • JVM笔记-Java技术体系与JVM概述

    Java 的广告词为 "一次编写,到处运行",之所以能够做到"跨平台",是因为每个平台上不同的虚拟机屏蔽了硬件的差异,而 Java 程序则是运行在虚拟机之上的。

    WriteOnRead

扫码关注云+社区

领取腾讯云代金券