JAVASCRIPT算法（4）

GraphQuery 發(fā)布于2019-08-21 17:54 / 748人閱讀

摘要：繼續(xù)學(xué)習(xí)鏈表的算法鏈接題目描述刪除單鏈表倒數(shù)第個節(jié)點(diǎn)，，盡量在一次遍歷中完成。如果條件是，那么被刪除的點(diǎn)就是，但是這樣刪不掉。思路很相似，那么三分之一，四分之一，五分之一，或者均分三段，均分四段也是類似的想法。

繼續(xù)學(xué)習(xí)鏈表的算法鏈接

題目描述：刪除單鏈表倒數(shù)第 n 個節(jié)點(diǎn)，1 <= n <= length，盡量在一次遍歷中完成。

分析：看到題目時的第一想法是先遍歷一次計(jì)算出單鏈表的長度 length，然后在遍歷第二次刪除第 length - n + 1 個節(jié)點(diǎn)，但是這需要遍歷兩次。正常的刪除第 n 個節(jié)點(diǎn)只需要遍歷一次就可以，如何只遍歷一次找到倒數(shù)第 n 個節(jié)點(diǎn)呢？可以設(shè)置兩個指針 p1、p2，首先 p1 和 p2 都指向 head，p2 移動到第 n 個節(jié)點(diǎn)，然后 p1 和 p2 同時向后移動，當(dāng) p2 移動到末尾時，p1 剛好指向倒數(shù)第 n 個節(jié)點(diǎn)。因?yàn)樽詈笠獎h除倒數(shù)第 n 個節(jié)點(diǎn)，所以可以找到倒數(shù)第 n + 1 個節(jié)點(diǎn)，方便刪除節(jié)點(diǎn)。這種思想在學(xué)校的時候?qū)W習(xí)過，還是蠻有用的吧，還是可以學(xué)到很多東西的，只不過總是找了很多借口。

 function Node(val){ //class的定義好像有點(diǎn)沒弄好
     this.val = val;
     this.next = null;
   }
    
   function removeNthNodeFromEnd(head, location){
     if(head == null) return head;
     var pointer1 = head;
     var pointer2 = head;
     for(var i = 0 ; i < location; i ++ ){
       pointer2 = pointer2.next;
       if(pointer2==null&&i!=location-1)
       return null; //如果根本沒有n個元素，就沒有倒數(shù)第n個元素
     }
     if(pointer2==null){  //總共就n個元素，那么head就是要刪除的那個點(diǎn)，返回下一個節(jié)點(diǎn)作為頭節(jié)點(diǎn)就好了。
       return pointer1.next;
     }
     while(pointer2.next!=null){ //如果條件是pointer2!=null，那么被刪除的點(diǎn)就是pointer1，但是這樣刪不掉。所以應(yīng)該記錄要刪除的節(jié)點(diǎn)的上一個節(jié)點(diǎn)。
       pointer2=pointer2.next;
       pointer1=pointer1.next;
     }
     pointer1.next = pointer1.next.next;//
     return head;

   }

我自己測試了下，測試用例如下，可能構(gòu)建鏈表的過程有點(diǎn)傻。

   var head = new Node("head");
   var current = head,next = null;
   for(var i =5 ; i >0 ; i--){
     next = new Node(i);
     current.next = next;
     current = next;
   }
   function showLinkedNode(head){
     if(head==null) console.log("head is "+head);
     while(head!=null){
       console.log(head.val);
       head = head.next;
     }
   }
    showLinkedNode(head);
    var result = removeNthNodeFromEnd(head,6);
    showLinkedNode(result);

結(jié)果是 head 5 4 3 2 1 和 5 4 3 2 1
如果removeNthNodeFromEnd(head,7)，返回的是null。

   showLinkedNode(head);
   var result = removeNthNodeFromEnd(head,3);
   showLinkedNode(result);

結(jié)果是head 5 4 2 1
還是得自己動手寫寫，可能以前能懂，但是過了一段時間以后就不懂了，讓往日的自己和后面的自己隔著時間對話。人并不總是在進(jìn)步，每一個時間點(diǎn)的思考以及結(jié)論都很有意義。

類似的問題
題目描述：求單鏈表的中間節(jié)點(diǎn)，如果鏈表的長度為偶數(shù)，返回中間兩個節(jié)點(diǎn)的任意一個，若為奇數(shù)，則返回中間節(jié)點(diǎn)。

分析：這道題的思路和第 3 題「刪除單鏈表倒數(shù)第 n 個節(jié)點(diǎn)」很相似。如果要求只能遍歷一遍鏈表的花，也通過兩個指針來完成。兩個指針從頭節(jié)點(diǎn)開始，慢指針每次向后移動一步，快指針每次向后移動兩步，直到快指針移動到尾節(jié)點(diǎn)時，慢指針移動到中間節(jié)點(diǎn)。思路很相似，那么三分之一，四分之一，五分之一，或者均分三段，均分四段也是類似的想法。

  function findMiddleNode(head){
     if(head==null||head.next==null) return head;
     var fastPoint = head;
     var normalPoint = head;
     while(fastPoint!=null&&fastPoint.next!=null){
           fastPoint = fastPoint.next.next;
           normalPoint = normalPoint.next;
     }
     return normalPoint;
   }

這個感覺比較簡單。