• <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
            非常感謝你指出其中的錯誤
            久久久久久国产精品免费免费 | 婷婷五月深深久久精品| 久久91精品国产91| 久久久亚洲欧洲日产国码二区| 久久99热只有频精品8| 精品人妻伦一二三区久久| 久久精品日日躁夜夜躁欧美| 久久99精品国产麻豆| 日韩十八禁一区二区久久| 久久久女人与动物群交毛片| 久久人人爽人爽人人爽av| 欧洲成人午夜精品无码区久久| 久久精品这里只有精99品| 久久99亚洲网美利坚合众国| 久久毛片一区二区| 中文精品久久久久国产网址| 久久AV高潮AV无码AV| 久久高清一级毛片| 9999国产精品欧美久久久久久| 99精品国产综合久久久久五月天| Xx性欧美肥妇精品久久久久久| 狠狠综合久久综合88亚洲| 久久久无码精品亚洲日韩软件| 久久99热只有频精品8| 伊人色综合久久天天人手人婷| 久久久艹| 久久国产一片免费观看| 九九99精品久久久久久| A级毛片无码久久精品免费| 婷婷久久五月天| 久久综合色老色| 久久天天躁狠狠躁夜夜不卡| 久久精品女人天堂AV麻| 久久精品国产亚洲AV不卡| 久久国产福利免费| 久久久精品日本一区二区三区| 国产午夜精品久久久久九九电影| 91久久精品视频| 国内精品久久久久久中文字幕| 成人国内精品久久久久影院VR| 久久se精品一区精品二区|