JAVASCRIPT算法（6）

FreeZinG 發(fā)布于2019-08-21 17:56 / 3448人閱讀

摘要：還是鏈表算法題目描述給出兩個無環(huán)單鏈表判斷和是否相交。所以可以得出另外一種解法，先遍歷鏈表，記住尾節(jié)點，然后遍歷鏈表，比較兩個鏈表的尾節(jié)點，如果相同則相交，不同則不相交。想法還是奇妙的。算法寫起來不難，難的是想到這個。

還是鏈表算法

題目描述：給出兩個無環(huán)單鏈表
A: a1 → a2

             ↘
               c1 → c2 → c3 → null
             ↗

B: b1 → b2 → b3
判斷 A 和 B 是否相交。
除了轉(zhuǎn)化為環(huán)的問題，還可以利用“如果兩個鏈表相交于某一節(jié)點，那么之后的節(jié)點都是共有的”這個特點，如果兩個鏈表相交，那么最后一個節(jié)點一定是共有的。所以可以得出另外一種解法，先遍歷 A 鏈表，記住尾節(jié)點，然后遍歷 B 鏈表，比較兩個鏈表的尾節(jié)點，如果相同則相交，不同則不相交。時間復(fù)雜度為 O(Length(A) + Length(B))，空間復(fù)雜度為 O(1)，思路比解法 2 更簡單。想法還是奇妙的。算法寫起來不難，難的是想到這個。

 function hasSharedNode(head1, head2){
     if(head1 == null||head2 == null) return false;
     var lastNode1 = head1;
     while(lastNode1.next != null){
       lastNode1 = lastNode1.next;
     }
     var lastNode2 = head2;
     while(lastNode2.next != null){
       lastNode2 = lastNode2.next;
     }
     if(lastNode1 == lastNode2){
     return true;
     }
     else {
     return false;
     }
   }

兩個鏈表相交擴展：判斷兩個有環(huán)單鏈表是否相交

題目描述：上面的問題是針對無環(huán)鏈表的，如果是鏈表有環(huán)呢？

分析：如果兩個有環(huán)單鏈表相交，那么它們一定共有一個環(huán)。因此可以先用之前快慢指針的方式找到兩個鏈表中位于環(huán)內(nèi)的兩個節(jié)點，如果相交的話，兩個節(jié)點在一個環(huán)內(nèi)，那么移動其中一個節(jié)點，在一次循環(huán)內(nèi)肯定可以與另外一個節(jié)點相遇。
有環(huán)單鏈表到底是咋樣的，就是我們前面說的小b型的結(jié)構(gòu)吧。尾節(jié)點的next指向前面的某個節(jié)點。如果交點不是在環(huán)上，那么肯定是共享一段直線加上一個環(huán)。
如果交點是在環(huán)上，那么就是共享環(huán)，直線階段是各自獨立的。所以結(jié)果就是共有一個環(huán)。需要用到上次找環(huán)入口的那個function。為啥不能用無環(huán)鏈表的算法呢？因為沒法判斷尾節(jié)點。其實也算是用到了，其實環(huán)入口就算是尾節(jié)點吧。

   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;
}

function hasSharedNodeWithLoop(head1, head2){
  var loopPort1 = findLoopPort(head1); //head1 head2的null之類的已經(jīng)在findLoopPort里面判斷了。
  var loopPort2 = findLoopPort(head2);
  if(loopPort1 == null || loopPort2 == null){ //無環(huán)，則不滿足條件，即使無環(huán)單鏈表相交，也返回false
    return false;
  }
  var startNode = loopPort1;
  while(loopPort1.next != startNode){ //保證只在環(huán)內(nèi)轉(zhuǎn)一圈
    if(loopPort1 == loopPort2)
     return true;
     loopPort1 = loopPort1.next;
  }
  return false; //轉(zhuǎn)完一圈沒發(fā)現(xiàn)共同的節(jié)點，則沒相交點。
}

兩個鏈表相交擴展：求兩個無環(huán)單鏈表的第一個相交點

LeetCode 160. Intersection of Two Linked Lists
題目描述：找到兩個無環(huán)單鏈表第一個相交點，如果不相交返回空，要求在線性時間復(fù)雜度和常量空間復(fù)雜度內(nèi)完成。我的想法是如果求得最后一個尾節(jié)點，然后讓尾節(jié)點的next指向其中的一個的頭，那么肯定就構(gòu)成了一個有環(huán)單鏈表。然后求得環(huán)的入口就是第一個相交點。主要是感覺一步一步的，好像都在復(fù)用前面的東西。所以就想到了這個。