JAVASCRIPT算法（5）

ysl_unh 發(fā)布于2019-08-21 17:55 / 804人閱讀

摘要：繼續(xù)鏈表算法有點(diǎn)恍恍惚惚。兩個(gè)指針先后進(jìn)入環(huán)里面，一個(gè)比另一個(gè)每次快一步，是不是一定會(huì)遇上。只是為了保證可以執(zhí)行操作。反正走了步相遇，那么快的領(lǐng)先慢的步，正好是一圈的長(zhǎng)度。所以如果快節(jié)點(diǎn)從頭開始和慢節(jié)點(diǎn)以一樣的一格一格跑，必在入口處相遇。

繼續(xù)鏈表算法
有點(diǎn)恍恍惚惚。

題目描述：判斷一個(gè)單鏈表是否有環(huán)

分析：還是通過快慢指針來解決，兩個(gè)指針從頭節(jié)點(diǎn)開始，慢指針每次向后移動(dòng)一步，快指針每次向后移動(dòng)兩步，如果存在環(huán)，那么兩個(gè)指針一定會(huì)在環(huán)內(nèi)相遇。首先單鏈表有環(huán)是什么一種結(jié)構(gòu)呢？小b這種結(jié)構(gòu)么？因?yàn)橹荒苁菃畏较虻闹敢?，所以?yīng)該是小b這種結(jié)構(gòu)。兩個(gè)指針先后進(jìn)入環(huán)里面，一個(gè)比另一個(gè)每次快一步，是不是一定會(huì)遇上。是的。那么如果快兩步呢？就是一個(gè)指針每次走3步，另一個(gè)每次走一步？相遇的話，快的那個(gè)是不是一定領(lǐng)先慢的那個(gè)若干個(gè)圈的長(zhǎng)度？假設(shè)經(jīng)過x步相遇，那么領(lǐng)先2x個(gè)節(jié)點(diǎn)。所以圈內(nèi)節(jié)點(diǎn)數(shù)一定要是偶數(shù)才行？先想題目吧。

  function linkedListWithCircle(head){
      if(head==null||head.next==null) return false;
      var fastNode = head;
      var normalNode = head;
      while(fastNode!=null&&fastNode.next!=null){//只是為了保證可以執(zhí)行fastNode.next.next操作。避免null.next錯(cuò)誤。
          fastNode = fastNode.next.next;
          normalNode = normalNode.next;
          if(normalNode==fastNode) return true;
      }
      return false;
  }

題目描述：判斷單鏈表是否有環(huán)，如果有，找到環(huán)的入口點(diǎn)

分析：由上題可知，按照 p2 每次兩步，p1 每次一步的方式走，發(fā)現(xiàn) p2 和 p1 重合，確定了單向鏈表有環(huán)路了。接下來，讓 p2 回到鏈表的頭部，重新走，每次步長(zhǎng)不是走 2 了，而是走 1，那么當(dāng) p1 和 p2 再次相遇的時(shí)候，就是在環(huán)路的入口點(diǎn)。加深思考。

 function findLoopPort(head){
      if(head==null||head.next==null) return null;
      var fastNode = head;
      var normalNode = head;
      var hasCircle = false;
      while(fastNode != null&&fastNode.next != null){
          fastNode = fastNode.next.next;
          normalNode = normalNode.next;
          if(normalNode == fastNode) {
              hasCircle = true;
              break;
          }
      }
      if(!hasCircle) return null;//原本想return false，后來發(fā)現(xiàn)還是null好。
      var fastNode = head;
      while(fastNode != normalNode){
          fastNode = fastNode.next;
          normalNode = normalNode.next;
      }
      return fastNode;
  }

想畫個(gè)圖來著。還是算了吧。反正走了x步相遇，那么快的領(lǐng)先慢的x步，正好是一圈的長(zhǎng)度。
假設(shè)從頭節(jié)點(diǎn)到圈的入口要走m步，那么慢節(jié)點(diǎn)在圈內(nèi)走了x-m步，從相遇的節(jié)點(diǎn)到入口節(jié)點(diǎn)，差x-(x-m)=m步。
所以如果快節(jié)點(diǎn)從頭開始和慢節(jié)點(diǎn)以一樣的一格一格跑，必在入口處相遇。
還是畫個(gè)圖吧。