JAVASCRIPT算法（6）

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

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

還是鏈表算法

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

             ↘
               c1 → c2 → c3 → null
             ↗

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

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

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

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

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

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é)點(diǎn)，則沒相交點(diǎn)。
}

兩個(gè)鏈表相交擴(kuò)展：求兩個(gè)無環(huán)單鏈表的第一個(gè)相交點(diǎn)

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