• <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>

            Life is Good.

            Enhance Tech and English
            隨筆 - 65, 文章 - 20, 評論 - 21, 引用 - 0
            數據加載中……

            單線鏈表常見操作

            1.單線鏈表倒序/逆序:
            struct Node
            {
                int data;
                Node* next;
            };

            Node* Reverse(Node* head)
            {
                struct Node *prep,*nowp,*nextp;

                prep=NULL;
                nowp=head;

                while(nowp!=NULL)
                {
                    nextp=nowp->next;
                    nowp->next=prep;
                    prep=nowp;
                    nowp=nextp;
                }

                return prep;
            }

            2. 判斷單向鏈表是否有環。下圖的三種情形都視為有環,算法必須能處理它們。


            01) 如果知道鏈表長度, 則可以遍歷鏈表, 遍歷次數大于長度, 就是有環了

               int iLength; 鏈表長度, 已知
               int i = 0;
               while (p != NULL)
               {
                   i ++;
                   if (i > iLength)
                   {
                       break;
                       return;
                   }
               }

            02)解法:設置兩個指針,一個每次向前跳一步,一個跳兩步,如果它們相遇,則有環。


            bool fLinkedListHasCircle(const Node* p)
            {
             bool flag = false;
             
             const Node* slowIterator = p;
             const Node* fastIterator = p;

             while(slowIterator && fastIterator->next)
             {
              slowIterator = slowIterator->next;
              fastIterator = fastIterator->next->next;
              if (slowIterator == fastIterator)
              {
               flag = true;
               break;
              }
             }
             return flag;
            }

            快速證明算法的正確性:

            考慮一般的情形,假設環上有n個結點,把它們從0到n-1編號,假設slowIterator達到節點0時,fastIterator領先 slowIterator的距離為m,我們知道fastIterator在一圈之內必能追上slowIterator。假設x跳以后 fastIterator追上slowIterator,此時slowIterator所在的結點編號為x,而fastIterator所在的節點編號為 m+2x-n:

            x = m+2x-n
            x = n-m

            所以經過n-m跳后,fastIterator追上slowIterator。


            posted on 2010-10-19 16:26 Mike Song 閱讀(248) 評論(0)  編輯 收藏 引用

            武侠古典久久婷婷狼人伊人| 久久久久国产精品| 中文字幕精品久久| 国产99久久久国产精品小说| 亚洲精品国产字幕久久不卡| 久久免费精品一区二区| 欧美激情精品久久久久久久九九九| 久久久久亚洲AV片无码下载蜜桃| 久久久久久人妻无码| 久久久久久极精品久久久| 国产激情久久久久久熟女老人| 成人久久精品一区二区三区| 深夜久久AAAAA级毛片免费看| 久久精品人成免费| 久久亚洲精品国产亚洲老地址 | 尹人香蕉久久99天天拍| 国产精品久久影院| 97精品国产97久久久久久免费| 久久精品不卡| 亚洲国产精品久久久久网站 | 久久精品女人天堂AV麻| 亚洲AV日韩精品久久久久久| 国产福利电影一区二区三区久久久久成人精品综合 | 国产精品无码久久久久| 久久久久久午夜成人影院| 国产精品久久久久蜜芽| 国产精品成人精品久久久 | 精品久久8x国产免费观看| 久久国产亚洲精品| 久久婷婷五月综合成人D啪 | 久久中文字幕人妻丝袜| 理论片午午伦夜理片久久 | 午夜精品久久久久久影视777 | 伊人热热久久原色播放www| 精品久久久无码中文字幕天天| 青青青国产精品国产精品久久久久| 久久亚洲AV成人无码国产| 亚洲色大成网站www久久九| 久久久久久久波多野结衣高潮 | 久久午夜福利电影| 欧美精品丝袜久久久中文字幕 |