JAVASCRIPT算法（6）

FreeZinG 發布于2019-08-21 17:56 / 3385人閱讀

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

還是鏈表算法

題目描述：給出兩個無環單鏈表
A: a1 → a2

             ↘
               c1 → c2 → c3 → null
             ↗

B: b1 → b2 → b3
判斷 A 和 B 是否相交。
除了轉化為環的問題，還可以利用“如果兩個鏈表相交于某一節點，那么之后的節點都是共有的”這個特點，如果兩個鏈表相交，那么最后一個節點一定是共有的。所以可以得出另外一種解法，先遍歷 A 鏈表，記住尾節點，然后遍歷 B 鏈表，比較兩個鏈表的尾節點，如果相同則相交，不同則不相交。時間復雜度為 O(Length(A) + Length(B))，空間復雜度為 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;
     }
   }

兩個鏈表相交擴展：判斷兩個有環單鏈表是否相交

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

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

   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，后來發現還是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之類的已經在findLoopPort里面判斷了。
  var loopPort2 = findLoopPort(head2);
  if(loopPort1 == null || loopPort2 == null){ //無環，則不滿足條件，即使無環單鏈表相交，也返回false
    return false;
  }
  var startNode = loopPort1;
  while(loopPort1.next != startNode){ //保證只在環內轉一圈
    if(loopPort1 == loopPort2)
     return true;
     loopPort1 = loopPort1.next;
  }
  return false; //轉完一圈沒發現共同的節點，則沒相交點。
}

兩個鏈表相交擴展：求兩個無環單鏈表的第一個相交點

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

GPU云服務器云服務器 javascript_es6 javascript算法題 6.7 6.6

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/90233.html

優秀程序員都應該學習的 GitHub 上開源的數據結構與算法項目

摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

cheukyin 2019-08-26 10:17 評論0 收藏0
【你該懂一點Javascript算法系列】之單源最短路徑 - Dijkstra算法

摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。 Javascript算法系列 - 單源最短路徑 - Dijkstra算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有...

SoapEye 2019-08-23 15:04 評論0 收藏0
javascript中可能用到的算法排序

摘要：因為是在已經分組排序過的基礎上進行插入排序，所以效率高。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。形成左右兩個分區，再遞歸按之前的步驟排序。算法復雜度不是科班生的我，第一次看見時間復雜度之類的名詞表示很懵逼，所以就找了網上的資料補習了下：時間復雜度：是指執行算法所需要的計算工作量空間復雜度：是指算法在計算機內執行時所需存儲空間的度量排序算法穩定性：假定在待...

Bamboy 2019-08-21 15:47 評論0 收藏0
排序算法回顧（JavaScript）

摘要：回顧選擇排序，插入排序，冒泡排序，快速排序，希爾排序，歸并排序，堆排序以及如何計算時間復雜度學習文章同學的描述數據結構等同學的十大經典算法本文代碼也上傳到了排序算法回顧。但希爾排序是非穩定排序算法。回顧選擇排序，插入排序，冒泡排序，快速排序，希爾排序，歸并排序，堆排序以及如何計算時間復雜度學習文章：hahda同學的javascript描述數據結構、hustcc等同學的十大經典算法 ...

jlanglang 2019-08-22 15:31 評論0 收藏0
JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言算法為王。想學好前端，先練好內功，內功不行，就...

zsy888 2019-08-26 10:27 評論0 收藏0
JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言算法為王。想學好前端，先練好內功，...

canger 2019-08-26 10:15 評論0 收藏0