精华内容
下载资源
问答
  • 如何判断链表结束
    2021-12-12 17:28:39

    一、问题概述

            环形链表就是在链表中存在环的情况,如果出现了环形链表,在程序中可能造成死循环的情况,导致严重的损失,因此需要判断一个链表是否成了环。如果有条件,可以为链表的节点设置一个visit属性,记录每次访问的次数,访问过一次就加1,如果出现了节点的访问次数为2,说明一定存在环。但有时,我们并不需要为该操作去修改弥足珍贵的数据结构,下面我们采用三种方法讲解如何求解环形链表的问题

    二、求解方法

            我们先假设链表的数据结构如下:(来源于Leetcode141题)

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */

    一、基于循环次数判断的暴力方法

            如果一个链表不成环,那么它就是可以穷尽的,我们假定你的链表的节点的个数小于10^4个,如果比这个还多的话,也许你需要用到树型结构了,不然你的速度会比乌龟还慢。

            因此我们可以一直循环,循环的时候,要么是因为到达了指针的尾部NULL,要么是因为循环次数太多超越了节点的个数,循环结束时判断循环次数就可以了。
            C++代码如下:

    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if(head==NULL){
                return 0;//没有环
            }
            struct ListNode * temp = head->next;
            int count=0;
            while(temp!=NULL&&count<100001){
               temp=temp->next;
               count++;
            }
            if(count>=100001){
                return 1;
            }
            return 0;
        }
    };

    二、借助Hash表

            每次访问节点的时候都判断是否在hash表中,如果没有就加入,如果存在就说明有环,如果没有环,一个节点只可能被访问一次,这和我们企图修改链表的数据结构去维护访问次数是等价的,只是以一种不影响节点内容的方式去完成。
            Java代码如下:

    public class Solution{
        public boolean hasCycle(ListNode head){
            //利用hash表保存 看该数组是否被遍历过
            Set<ListNode> buf = new HashSet<ListNode>();
            while(head!=null){
                if(!buf.add(head)){
                    return true;
                }
                head=head.next;
            }
            return false;
        }
    }
    
    

    三、快慢指针 

            其实到这里,才是本问题最精彩的解法(前面都是在扯淡),这个方法十分精巧,是伟大的数学家Floyd发明的,即快慢指针的解法。

            基于Floyd环的思想,定义两种类型的指针,slow慢指针前进步长为1,快指针前进步长为2(在第一次前进后要判断前进后是否到达了NULL)。这样,如果在循环的过程中,快指针追上了慢指针,那么说明成了环。其中为什么一定能追上的具体的数学证明需要沉下心来仔细Google。

            C语言代码如下:

    bool hasCycle(struct ListNode *head) {
        if(head==NULL){
            return 0;//不成环
        }
        //快慢指针
        struct ListNode * slow = head;
        struct ListNode * fast = head;
        while(fast!=NULL){
            //fast比slow快 只需要判断fast有没有越界就可以了
            slow = slow->next;
            fast = fast->next;
            if(fast!=NULL){
                fast=fast->next;//避免操纵空指针
            }
            else{
                break;
            }
            //放在后面 处理初始状态
            if(slow==fast){
                return 1;//成环
            }
        }
        return 0;
    }
    

            此外,为什么笔者要这么蛋疼写三种解法和三种不同的语言求解呢?其实本人就是从菜鸡算法一步步向大佬算法挖掘的,只有一步一步走,才能到达幸福的彼岸。同时,用多种语言也旨在说明,算法是一种思想,语言只是一种工具。

            多谢大家指正,共勉! 

    更多相关内容
  • 判断链表是否有环

    2021-01-29 13:26:23
    判断一个单向链表是否有环。(指向表头结点的指针为head)方法一:(1)用两个指针p1和p2分别指向表头结点,即p1=p2=head(2)p1和p2分别采用1和2作为步长遍历该链表。(注意,p2应该检查当前结点的下一个结点是否为NULL)(3...

    判断一个单向链表是否有环。(指向表头结点的指针为head)

    方法一:

    (1)用两个指针p1和p2分别指向表头结点,即p1=p2=head

    (2)p1和p2分别采用1和2作为步长遍历该链表。(注意,p2应该检查当前结点的下一个结点是否为NULL)

    (3)如果p1或者p2遇到了NULL,则证明该链表没有环;若p1和p2在某时刻指向同一结点,则说明该链表有环。

    点击(此处)折叠或打开

    bool I***itsLoop(slist * head)

    {

    slist * slow = head , * fast = head;

    while ( fast && fast -> next )

    {

    slow = slow -> next;

    fast = fast -> next -> next;

    if ( slow == fast ) break ;

    }

    return ! (fast == NULL || fast -> next == NULL);

    }

    (4)若该表有环,

    (a)设从表头结点(包括)开始到环开始的结点(不包括)共 有l1个结点;设从环开始结点(包括)到它们相遇的结点(不包括)共有l2个结点;设从他们第一次相遇的结点开始(包括)到环开始结点(不包括)共有l3个结点;设整个环共有c个结点。则有c=l2+l3,且l1+l2即为它们第一次相遇时,p1所遍历的结点个数。

    (b)当它们第一次相遇时,固定p2,然后p1以1为步长继续遍历此表,则他们再次相遇时,p1从上次相遇到这次相遇所经过的总步长即为环中结点的个数c。

    (c)可以证明,当他们第一次相遇时,p1不可能经过环开始结点两次,即不可能开始第二次遍历环。设当它们第一次相遇时,p2已经把环遍历了k遍(k>=1)则有:2(l1+l2) = l1+l2+kc,即l1+l2=kc

    (d)l1+l2=kc=>l1=(k-1)c+l3

    (e)固定p2在它们第一次相遇的结点,然后p1回到表头,然后它们均以1为步长遍历链表,则它们第一次相遇时,即为环开始结点

    方法二:

    (a)p从表头结点开始以1为步长遍历表,边遍历边将表反向

    (b)如果p遇到NULL,则说明表没有环

    (c)如果p最后等于head,则说明表有环,且记此时p所经过的表的结点数为l(l=2l1+c,l1和c的定义见方法一)

    (d)p再从表头结点开始以1为步长遍历表,边遍历边反向,当遍历到l/2时,停止,设两个指针p1,p2均指向当前结点,然后分别从两个方向同时以1为步长遍历表(其中一个需要边遍历,边反向链表),当他们第相遇时,当前结点即为环头结点。且此时链表还原成原来的链表。

    转自:http://hi.baidu.com/coolxiaoqin/blog/item/df06373e50dcb5ff838b13aa.html

    第三种方法(通过修改链表,最终可还原链表,且可去掉链表中的环)

    或许可以再构造了一个双向链,但不存储原来的数据而存储节点指针:

    typedef struct _PtrLinkNode

    {

    LinkNode* theNode;

    struct _PtrLinkNode* prev;

    struct _PtrLinkNode* next;

    } PtrLinkNode;

    然后在逆转链表时把当前节点指针加入到这个双向链表中。当逆转结束时如果这个双向链表的首尾的theNode不相等,则说明没有死链,再逆转回来就可以了;如果相等,则存在死链,再在这个双向链表从两端向中间进行首尾比较,直到遇到不相等的两个节点,这两个节点形成的闭区间就是原来形成死链的节点,顺序与现在在双向链表中的顺序相同。把双向链表中位于这个区间之后的节点支掉,然后按双向链表的顺序重建链表就可以恢复出原来的链表并去除死链。时间复杂度和空间复杂度都是O(N)。

    =====================================================

    几大派系的算法:

    herryhuang(Herry)派:

    『圆子示踪法』

    每隔N个接点,插入一个示踪圆子。如果找到示踪圆子,那么就说明在该示踪圆子之前存在死链,再怎么找到确却的死链位置,有待探讨;找完死链以后再把示踪圆子删除;

    plainsong(短歌)派:

    『查表法』

    顺着接点往下走,每走一个,查找记录接点值是否存在,若存在,则有死链,且该接点就是死链位置,否则,记录接点值。

    老迈派:

    『指针追赶法』

    用两个指针指向头接点,然后顺次遍历连表,一个步进1,一个步进2,相遇且不是null,则有死链。相遇时都是null,则没有。如果没有死莲,两个指针是不会相遇的,除非在两头。

    注:原子示踪法中 示踪原子的插入方法

    void* flags[MAX];

    使用的时候这样

    比如原来是:

    a1->next == a2

    那么现在就是

    a1->next == &flags[k];

    flags[k] == a2;

    这样,拿到一个指针p后,只需要判断

    if(p >= flags && p <= &flags[MAX])

    即可判断他是不是一个标志节点,这个跟具体结构没有任何关系

    方法时间空间复杂度:

    再一个死循环里发现结论的最大时间为 K + N, (K 步长, N死循环长度,M死循环位置)

    而在这之前的复杂度为M, 所以复杂度最大为M + K + N, K越小时间越小

    但是空间复杂度至少为(M + N)/K, 就要看怎么均匀这两者.

    而且如果要求对链表只能读,也不能够应用

    老迈的算法,时间复杂不如你的,但是它的空间复杂度几乎为0

    老迈的总结:

    大家讨论得差不多了吧,其实如果仔细看看上面的发言,就会发现后来的各位所讨论的东西已经有充分的讨论了,其实如果仅仅要判断链表是不是死链(这就是楼主的要求嘛),老迈的方法肯定比我的快,因为我访问的每一个节点至少要做三到四次比较(各位写出代码来接明白了),而老迈的只需要两次。另外,我的方法申请空间肯定是要费时间的。如高要找出那个出问题的节点,则我的方法就比较快了,因为将插入的节点放在线形表中。

    如下,插入节点的步长为Setp,存放这些插入的节点的线形表为p[]

    如果在插入p[m]之后,碰到了曾经插入的节点p[n],则可以断定,出问题的节点位于p[n-1]到p[m]之间,而它指向的位置,位于p[m - 1]到p[m]之间,这是个常量,最多再进行2*Step*step次比较即可找到这个节点。这是个常数。

    所以,我的方法的关键问题在于找到一个合理的方法存放线形表,刚才编了半天,很麻烦,呵呵,下午还有事,各位继续发言,有时间的话写一个出来大家看看,我先撤了。

    ============================================

    三个派系的比较:

    本帖的三大派别:

    plainsong(短歌)派:

    『查表法』

    顺着接点往下走,每走一个,查找记录接点值是否存在,若存在,则有死链,且该接点就是死链位置,否则,记录接点值。

    —>这个似乎,虽然查找复杂度 最大仅 为 N,但是空间..汗汗..的确比较大

    herryhuang(Herry)派:

    『圆子示踪法』

    每隔N个接点,插入一个示踪圆子。如果找到示踪圆子,那么就说明在该示踪圆子之前存在死链,再怎么找到确却的死链位置,有待探讨;找完死链以后再把示踪圆子删除;

    —>如果可以更改链表指针,个人认为这个办法是最好的,最大时间复杂度 N+K(K为步长),如果K设置成一个比较合理的值,应该能在时间和空间上都取得很好的效果(在前两个K点前加两个针指应该可以把确定链表的范围缩小到1K到2K之间吧

    老迈派:

    『指针追赶法』

    用两个指针指向头接点,然后顺次遍历连表,一个步进1,一个步进2,相遇且不是null,则有死链。相遇时都是null,则没有。如果没有死莲,两个指针是不会相遇的,除非在两头。

    –>这个办法,有最小的空间占用吧,确定有死链最大应该是2*N吧,确定位置应该有相应算法吧,估计是3N左右吧,如果是小型链表,这个办法应该比较好,但在巨型链表时,这个从速度上而言,反而不如第二种办法了吧.

    更多解法请见:http://topic.csdn.net/t/20040906/09/3343269.html#

    扩展问题:

    判断两个单链表是否相交,如果相交,给出相交的第一个点(两个链表都不存在环)。

    比较好的方法有两个:

    一、将其中一个链表首尾相连,检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个点。

    二、如果两个链表相交,那个两个链表从相交点到链表结束都是相同的节点,我们可以先遍历一个链表,直到尾部,再遍历另外一个链表,如果也可以走到同样的结尾点,则两个链表相交。

    这时我们记下两个链表length,再遍历一次,长链表节点先出发前进(lengthMax-lengthMin)步,之后两个链表同时前进,每次一步,相遇的第一点即为两个链表相交的第一个点。

    展开全文
  • 判断链表中是否有环

    2022-03-20 20:41:39
    bool hasCycle(struct ListNode *head) { ... //①假设链表不存在环: //1.当链表节点总个数为奇数个N时,则第二个节点到尾节点共有N-1偶数个节点(包括第二个节点) //则经过有限次2连跳,快指针将到

    题目链接https://leetcode-cn.com/problems/linked-list-cycle/

    bool hasCycle(struct ListNode *head) {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        //①假设链表不存在环:
        //1.当链表节点总个数为奇数个N时,则第二个节点到尾节点共有N-1偶数个节点(包括第二个节点)
        //则经过有限次2连跳,快指针将到达尾节点,此时由于fast->next ==NULL,故循环结束
    
        //2.当链表节点总个数为偶数个N时,则第二个节点到尾节点共有N-1奇数个节点(包括第二个节点)
        //则经过有限次2连跳,快指针将到达尾节点的前一个节点,此时循环继续,但进行到
        //fast = fast->next->next时,fast被赋予NULL,而结束循环
        //总结:假设链表无环,如果链表共奇数个节点,则不满足fast->next != NULL而结束循环
        //                  如果链表共偶数个节点,则不满足fast != NULL而结束循环
        while((fast != NULL) && (fast->next != NULL)){
            slow = slow->next;
            fast = fast->next->next;
            //如果快慢指针相遇,说明环存在
            if(slow == fast){
                return true;
            }
        }
        return false;
    }

    思路:采用快慢指针实现,如果存在环,快指针一定追上慢指针,如果不存在环,快指针走到链表尽头。


     假设存在环

         1. 假设存在环,如果slow每次走1步,而fast每次走2步,请问slow 和 fast是否一定会在环里面相遇?

              答:一定会。假设slow进入环时,这时fast 与 slow 相差 N 个节点,由于slow每次走1步,而fast每次走2步,故每走一次,fast 和 slow 之间距离减少1,一定会在未来某次中,该距离减为0,故一定会相遇。

           2. 假设存在环,且环中节点总数为sum,如果slow每次走1步,而fast每次走3步,请问slow 和 fast是否一定会在环里面相遇?

              答:不一定。假设slow进入环时,这时fast 与 slow 相差 N 个节点,由于slow每次走1步,而fast每次走3步,故每走一次,fast 和 slow 之间距离减少2.

              1)如果一开始N为奇数,则多次减2之后,这个距离就会变成-1(即fast是slow前的节点),如果这时环的总节点sum又是偶数,则下次追逐过程中,N的初始值再次变为奇数,如此往复,fast永远追不上slow.

              2)如果一开始N为偶数,则多次减2之后,这个距离就会变成0,这种情况下fast就能追上。

          

           3. 假设存在环,且环中节点总数为sum,如果slow每次走1步,而fast每次走4步,请问slow 和 fast是否一定会在环里面相遇?

              答:不一定。假设slow进入环时,这时fast 与 slow 相差 N 个节点,由于slow每次走1步,而fast每次走4步 故每走一次,fast 和 slow 之间距离减少3.多次走后,N可能是0,也可能是-1,也可能是-2,而导致后面也像2一样一直循环追不上。

    展开全文
  • 如何判断链表有环(三种方法)

    千次阅读 2019-06-02 09:16:15
    方法一、穷举遍历 ...点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的 节点,就继续遍历下一个新节点,继续重复刚才的操作。 例如这样的链表:A->B->...

    方法一、穷举遍历

    方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点重新遍历
    新节点之前的所有节点,用新节点ID和此节点之前所有节点ID依次作比较。如果发现新节点之前的所有节
    点当中存在相同节点ID,则说明该节点被遍历过两次,链表有环;如果之前的所有节点当中不存在相同的
    节点,就继续遍历下一个新节点,继续重复刚才的操作。
    
    例如这样的链表:A->B->C->D->B->C->D, 当遍历到节点D的时候,我们需要比较的是之前的节点A、
    B、C,不存在相同节点。这时候要遍历的下一个新节点是B,B之前的节点A、B、C、D中恰好也存在
    B,因此B出现了两次,判断出链表有环。
    
    假设从链表头节点到入环点的距离是D,链表的环长是S。那么算法的时间复杂度是0+1+2+3+…+(D
    +S-1) = (D+S-1)*(D+S)/2 , 可以简单地理解成 O(N*N)。而此算法没有创建额外存储空间,空间复
    杂度可以简单地理解成为O(1)。
    

    方法二、哈希表缓存

    ****首先创建一个以节点ID为键的HashSet集合,用来存储曾经遍历过的节点。然后同样是从头节点
    开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就用新节点和HashSet集合当中存储的
    节点作比较,如果发现HashSet当中存在相同节点ID,则说明链表有环,如果HashSet当中不存在相
    同的节点ID,就把这个新节点ID存入HashSet,之后进入下一节点,继续重复刚才的操作。
    
    这个方法在流程上和方法一类似,本质的区别是使用了HashSet作为额外的缓存。
    
    假设从链表头节点到入环点的距离是D,链表的环长是S。而每一次HashSet查找元素的时间复杂度
    是O(1), 所以总体的时间复杂度是1*(D+S)=D+S,可以简单理解为O(N)。而算法的空间复杂度还是
    D+S-1,可以简单地理解成O(N)。
    

    方法三、快慢指针

    首先创建两个指针1和2(在java里就是两个对象引用),同时指向这个链表的头节点。然后开始一
    个大循环,在循环体中,让指针1每次向下移动一个节点,让指针2每次向下移动两个节点,然后比
    较两个指针指向的节点是否相同。如果相同,则判断出链表有环,如果不同,则继续下一次循环。
    
    例如链表A->B->C->D->B->C->D,两个指针最初都指向节点A,进入第一轮循环,指针1移动到了节
    点B,指针2移动到了C。第二轮循环,指针1移动到了节点C,指针2移动到了节点B。第三轮循环,
    指针1移动到了节点D,指针2移动到了节点D,此时两指针指向同一节点,判断出链表有环。
    
    此方法也可以用一个更生动的例子来形容:在一个环形跑道上,两个运动员在同一地点起跑,一个运
    动员速度快,一个运动员速度慢。当两人跑了一段时间,速度快的运动员必然会从速度慢的运动员身
    后再次追上并超过,原因很简单,因为跑道是环形的。
    假设从链表头节点到入环点的距离是D,链表的环长是S。那么循环会进行S次(为什么是S次,有心的
    同学可以自己揣摩下),可以简单理解为O(N)。除了两个指针以外,没有使用任何额外存储空间,所
    以空间复杂度是O(1)。
    

    方法四、Set集合大小变化

    评论中有 @长沙小辣椒 同学指出:还可以用 set 遍历链表,把节点放入set里,每次访问下个节点时,
    如果set长度不变,则跳出,说明有环。否则set长度+1,继续遍历。
    该方法时间复杂度是O(N),空间复杂度上因为需要额外等数量的存储空间,所以空间复杂度是O(n)。
    

    如何找出有环链表的入环点?

    根据这篇文章:链表中环形的入口,我们来分析一下入环口和我们上面这个快慢指针相遇点的关系。
    当fast若与slow相遇时,slow肯定没有走遍历完链表(不是一整个环,有开头部分,如上图)或者恰好
    遍历一圈(未做验证,看我的表格例子,在1处相遇)。于是我们从链表头、相遇点分别设一个指针,
    每次各走一步,两个指针必定相遇,且相遇第一点为环入口点(慢指针走了n步,第一次相遇在c点,
    对慢指针来说n=s+p,也就是说如果慢指针从c点再走n步,又会到c点,那么顺时针的CB距离是n-p=s,
    但是我们不知道s是几,那么当快指针此时在A点一步一步走,当快慢指针相遇时,相遇点恰好是圆环
    七点B(AB=CB=s))。
    

    如何判断两个单链表是否相交,以及相交点?

    方法一、直接法

    直接判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(len1*len2),耗时很大
    

    方法二、利用计数

    如果两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识。因而判断
    两个链表中是否存在地址一致的节点,就可以知道是否相交了。可以对第一 个链表的节点地址
    进行hash排序,建立hash表,然后针对第二个链表的每个节点的地址查询hash表,如果它在ha
    sh表中出现,则说明两个链表有共 同的结点。这个方法的时间复杂度为:O(max(len1+len2);
    但同时还得增加O(len1)的存储空间存储哈希表。这样减少了时间复杂度,增加 了存储空间。
    以链表节点地址为值,遍历第一个链表,使用Hash保存所有节点地址值,结束条件为到最后一个
    节点(无环)或Hash中该地址值已经存在(有环)。再遍历第二个链表,判断节点地址值是否已
    经存在于上面创建的Hash表中。这个方面可以解决题目中的所有情况,时间复杂度为O(m+n),m
    和n分别是两个链表中节点数量。由于节点地址指针就是一个整型,假设链表都是在堆中动态创建
    的,可以使用堆的起始地址作为偏移量,以地址减去这个偏移量作为Hash函数
    

    方法三、利用有环链表思路

    对于两个没有环的链表相交于一节点,则在这个节点之后的所有结点都是两个链表所共有的。如果它
    们相交,则最后一个结点一定是共有的,则只需要判断最后一个结点是否相同即可。时间复杂度为O(
    len1+len2)。对于相交的第一个结点,则可求出两个链表的长度,然后用长的减去短的得到一个差值 
    K,然后让长的链表先遍历K个结点,然后两个链表再开始比较。还可以这样:其中一个链表首尾相连,
    检测另外一个链表是否存在环,如果存在,则两个链表相交,而检测出来的依赖环入口即为相交的第一个。
    
    展开全文
  • 设计算法判断链表是否中心对称

    千次阅读 热门讨论 2020-03-20 11:36:13
    算法思想:使用栈来判断链表中的数据是否中心对称。让链表的前一半元素依次进栈,在处理链表的后一半元素的时,当访问到链表的一个元素时,就从栈中弹出一个元素,两个元素比较,若相同,则将链表的下一个元素与栈中...
  • 【算法】如何判断链表有环

    万次阅读 多人点赞 2017-12-25 20:05:59
    如何用程序判断出这个链表是有环链表? 不允许修改链表结构。 时间复杂度O(n),空间复杂度O(1)。 方法一、穷举遍历方法一:首先从头节点开始,依次遍历单链表的每一个节点。每遍历到一个新节点,就从头节点...
  • 链表在数据结构与算法中可谓“北斗之尊”,现在让我们通过判断链表回文的小练习进一步更深地了解链表~ 文章目录一、链表的节点结构二、判断一个链表是否为回文结构(一)解法1:将链表全部节点进栈出栈比较(空间...
  • 【问题描述】学习链表,销毁链表总感觉没有成功,请问怎么确定链表确实被销毁了?为什么其余节点的内容没有变化? 【代码】 ``` #include #include #include struct link_list { int num; char name[20...
  • BM6 判断链表中是否有环 https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=295&sfm=html&channel=nowcoder 题目描述:判断给定的链表中是否有环。如果有环则返回true,否则返回...
  • 如何判断循环链表

    2020-08-31 00:12:06
    如何判断循环链表 实际上判断一个链表是否是循环的思路很简单,困扰我的反而是“带环链表是否就是循环链表”这个问题,穿梭于各中帖子、书本寻找答案终究找不到明确说明。《大话数据结构》中循环链表的定义为:“将...
  • 题目: 判断给定的链表中是否有环。...如果这个链表内存在环,那么慢指针和快指针一定会一直绕环移动,并且某个时刻一定会重合,此时判断结束,输出true 为什么一定会相遇??,我们假设环的长度
  • 如何判断链表有环

    千次阅读 2019-03-11 10:26:57
    如何判断单链表是否存在环 ...如何用程序判断出这个链表是有环链表? 不允许修改链表结构。 时间复杂度O(n),空间复杂度O(1)。 方法一、穷举遍历 方法一:首先从头节点开始,依次遍历单链表的每...
  • 快慢两个指针都从链表头开始遍历,于是快指针到达链表末尾的时候慢指针刚好到达中间位置,于是可以得到中间元素的值。快慢指针在链表相关问题中主要有两个应用: 快速找出未知长度单链表的中间节点 设置...
  • 数据结构---如何判定链表是否有环

    千次阅读 2022-03-29 22:21:48
    链表存在环时,通过直接遍历链表无法知道是否存在环。假设我们可以修改链表结构的话,可以在链表里加入访问的标记,当下一个节点已经被访问过就说明存在环。 方法一、穷举遍历 首先从头节点开始,依次遍历...
  • 判断循环双链表是否对称 二、解题思路 解题思路很简单,跟判断回文数的方法类似,只不过换成了链表。 首先需要写出循环双链表,第二,则判断是否对称 判断是否对称,定义两个指针,p1指针指向头指针的后继(头遍历...
  • 判断链表是否为回文链表

    千次阅读 2018-12-02 11:44:54
    2. 解决的方法有两种,一种是将链表进行翻转(这里可以使用递归来解决)然后翻转后的后半部分与链表的前半部分进行比较来进行判断,第二种是将先找到链表的中间位置,这里可以使用快慢指针指针来进行,快指针一次走...
  • 给定一个链表,判断链表中是否有环。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。 示例 1: 输入:head = [3,2,0,-4], pos ...
  • Python判断回文链表

    千次阅读 多人点赞 2021-12-28 20:37:55
    首先接收用户输入数字列表,每个数字用空格分隔,使用split截断字符串,使用map,把每个元素映射成int类型,然后再转成list,使用循环取出每项元素添加到链表中。 lt = list(map(int, s.split(' '))) 代码如下: ...
  • 采用暴力的方法,遍历两个链表判断第一个链表的每个结点是否在第二个链表中,时间复杂度为O(len1*len2),耗时很大。 2、hash计数法 如 果 两个链表相交,则两个链表就会有共同的结点;而结点地址又是结点唯一标识...
  • 判断链表是否有环,判断环的入口

    千次阅读 2018-09-13 16:59:44
    问题1:判断链表是否有环 问题分析 首先考虑环出现之后链表的特征,从头开始的链表遍历无法结束,也就是不存在尾节点 这时候第一个想法,一遍遍历链表,直至出现null 或者下一个元素是之前出现过的元素,那么...
  • 判断是否循环链表

    千次阅读 2019-05-24 14:52:21
    如何判断循环链表 实际上判断一个链表是否是循环的思路很简单,困扰我的反而是“带环链表是否就是循环链表”这个问题,穿梭于各中帖子、书本寻找答案终究找不到明确说明。《大话数据结构》中循环链表的定义为:“将...
  • 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。 示例...
  • 循环遍历一个链表时,终止条件的正确性尤为重要,它可以有效的避免链表指针在移动时出现空指针错误,以及正确解题。 而终止条件的确定依赖于问题的需求以及每次走的步数;其次,链表的节点个数也会影响终止条件,...
  • C语言实现链表贪吃蛇

    2020-12-17 04:41:46
    用C语言链表写的贪吃蛇(程序设计时做的,做的不好大佬勿喷) 借助游戏内容分析贪吃蛇所需的功能主要包括这几块: 1.移动光标模块 2.打印地图模块和基本规则信息 读取最高分文件 3.打印初始蛇模块 打印时给予蛇的...
  • C语言实现循环链表

    2020-12-17 09:13:14
    以及链表结束判断条件变成q是否等于尾指针。 2、注意传递的实参需要取地址 3、循环链表的优势在于双链表合并,以及实现尾插法简单(首先新建结点指向头结点,然后把尾指针的next域指向该新建结点) 4、在创建链表...
  • 设置p1为慢指针,p2为快指针,两者初始时都指向链表的头结点 ,慢指针p1每次前进1步,快指针p2每次前进2步。如果链表存在环,则快指针p2肯定先进入环,慢指针p1后进入环,两个指针必定会相遇。如果不存在环,则快...
  • 判断两个链表是否相交

    万次阅读 2018-08-30 21:51:56
    JAVA堆和栈比较 ...(1)将其中任意一个链表的环打破,即让尾结点指向null(记下保存原本应当指向的位置),然后判断第二个链表是否含有环,若第二个链表无环则相交,否则不相交 (2)利用判断单...
  • 此题需要我们判断链表中有没有环,解题思路依旧运用到快慢指针,快指针一次走两步,慢指针一次走一步,看这俩个指针会不会相遇,如果有环当 fast 走到链表尾时会转回来,有一时刻会与 slow 相遇,这样就可以判断链表...
  • 原地址 解题思路 定义双指针,分别指向A和B的头部。 如果链表一样长且有交点,则第一次遍历就能找到相同交点,...如果没有交点,则第二次遍历结束都是null,遍历结束,返回null a+b=b+a,最终一定都会指向null。 ..

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 124,185
精华内容 49,674
关键字:

如何判断链表结束

友情链接: Exam01.rar