• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            是技術(shù),更是藝術(shù)

            一心編程,就沒有解決不了的問題
            posts - 9, comments - 11, trackbacks - 0, articles - 0

            判斷單鏈表是否有環(huán)

            Posted on 2010-09-24 12:30 李熙建 閱讀(3172) 評論(4)  編輯 收藏 引用 所屬分類: C++

             

            typedef struct LNode
            {
                
            int data;
                LNode 
            *next;
            }
            LNode ;
            typedef LNode
            * LinkList;
            //單鏈表有環(huán)返回true 否則返回false
            bool is_looplist(LNode *head)
            {
                LNode 
            *fast,*slow;
                
            if (head == NULL || head->next == NULL)
                
            {
                    
            return false;
                }

                
            slow = head;fast = head->next;

                
            while(true)
                
            {
                    
            if(!fast || !fast->next)
                        
            return false;
                    
            //為了防止fast跨過slow的情況,在每次判斷的時(shí)候比較當(dāng)前節(jié)點(diǎn)和下一節(jié)點(diǎn)
                    else if (fast == slow || fast->next == slow)
                        
            return true;
                    
            else
                    
            {
                        slow 
            = slow->next;//一次跳一步
                        fast = fast->next->next;//一次跳兩步
                    }

                }

            }

            如果要返回環(huán)的入口節(jié)點(diǎn)
            一種效率比較低的方法是
            一個指針p1從表頭開始,指針p2 初始化為判環(huán)時(shí)找到的指針,p1每前進(jìn)一步,由p2遍歷一次環(huán)中各結(jié)點(diǎn),遍歷過程中每次都要判斷p1是否p2
            當(dāng)p2 == fast時(shí)候,p1 = p1.next,繼續(xù)循環(huán)。這樣肯定能找到入口,但是效率為O(n^2)

            Feedback

            # re: 判斷單鏈表是否有環(huán)  回復(fù)  更多評論   

            2010-09-25 08:16 by Algorics
            如果知道鏈表的結(jié)點(diǎn)數(shù)n,那么如果進(jìn)行n+1次找下一個結(jié)點(diǎn)還沒到鏈表的尾部的話就有環(huán)。

            # re: 判斷單鏈表是否有環(huán)  回復(fù)  更多評論   

            2010-09-26 21:46 by 李熙建
            @Algorics
            一般情況下,只已知鏈表的頭節(jié)點(diǎn),鏈表元素個數(shù)已知的情況下,你說的方法可以

            # re: 判斷單鏈表是否有環(huán)[未登錄]  回復(fù)  更多評論   

            2011-05-06 17:49 by kyle
            代碼有錯...永遠(yuǎn)返回TRUE.
            在對fast初始化的時(shí)候應(yīng)該是fast=head->next;

            # re: 判斷單鏈表是否有環(huán)  回復(fù)  更多評論   

            2011-08-01 09:14 by 李熙建
            @kyle
            非常感謝你指出其中的錯誤
            狠狠色丁香久久婷婷综合图片| 99精品国产99久久久久久97| 婷婷国产天堂久久综合五月| 久久中文字幕无码专区| 思思久久99热只有频精品66| 国内精品人妻无码久久久影院| 72种姿势欧美久久久久大黄蕉| AV无码久久久久不卡蜜桃| 国产精品一区二区久久精品无码| 久久精品国产72国产精福利| 久久久久亚洲AV成人网人人网站| 久久久久人妻一区二区三区vr| 国内精品免费久久影院| 亚洲人成网站999久久久综合| 久久免费精品视频| 亚洲va久久久久| 2021少妇久久久久久久久久| 久久久久国产精品人妻| 久久精品一区二区影院| 99久久人妻无码精品系列| 精品久久久久久中文字幕大豆网| 天天做夜夜做久久做狠狠| 91精品国产乱码久久久久久| 精品久久久无码人妻中文字幕| 国产成人精品久久综合| 久久久久久亚洲精品成人| 日本久久久久久久久久| 99久久精品九九亚洲精品| 亚洲乱码精品久久久久..| 女人高潮久久久叫人喷水| 久久无码国产| 亚洲精品国产综合久久一线| 色综合久久久久综合99| 久久久久国产亚洲AV麻豆| 精品99久久aaa一级毛片| 国产精品va久久久久久久| 国产精品久久久久久久午夜片| 国产亚洲精久久久久久无码AV| 久久亚洲国产精品一区二区| 99久久精品国产麻豆| 中文字幕一区二区三区久久网站|