• <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)  編輯 收藏 引用

            国产精品美女久久久久AV福利| 日韩电影久久久被窝网| 996久久国产精品线观看| 久久精品国产秦先生| 久久亚洲中文字幕精品一区| 亚洲综合伊人久久综合| 99久久久精品| 久久久久久国产精品美女| 久久精品国产一区| 国内精品伊人久久久久777| 99久久精品免费看国产一区二区三区| 亚洲国产日韩综合久久精品| 国产精品一区二区久久国产| 日批日出水久久亚洲精品tv| 99久久综合狠狠综合久久止| 久久亚洲AV无码精品色午夜麻豆| 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲高清不卡 国产成人精品久久亚洲 | 久久久久久亚洲精品不卡| 久久精品国产久精国产果冻传媒 | 天天做夜夜做久久做狠狠| 99久久精品毛片免费播放| 亚洲AV无码1区2区久久| 三级韩国一区久久二区综合| 国产精品久久国产精麻豆99网站 | 国产一久久香蕉国产线看观看 | 国产精品gz久久久| 91精品国产91久久综合| 久久人人爽人人爽人人AV东京热 | 久久国产亚洲精品麻豆| 久久永久免费人妻精品下载| 久久人妻AV中文字幕| 久久人做人爽一区二区三区 | 久久大香香蕉国产| 亚洲成色WWW久久网站| 久久精品国产99久久久古代| 天天综合久久一二三区| 久久久久久综合网天天| 国产69精品久久久久久人妻精品| 久久香综合精品久久伊人| 久久WWW免费人成一看片| 久久夜色精品国产噜噜麻豆|