資訊專欄INFORMATION COLUMN
摘要：繼續鏈表算法有點恍恍惚惚。兩個指針先后進入環里面，一個比另一個每次快一步，是不是一定會遇上。只是為了保證可以執行操作。反正走了步相遇，那么快的領先慢的步，正好是一圈的長度。所以如果快節點從頭開始和慢節點以一樣的一格一格跑，必在入口處相遇。
繼續鏈表算法
有點恍恍惚惚。
題目描述：判斷一個單鏈表是否有環
分析：還是通過快慢指針來解決，兩個指針從頭節點開始，慢指針每次向后移動一步，快指針每次向后移動兩步，如果存在環，那么兩個指針一定會在環內相遇。首先單鏈表有環是什么一種結構呢？ 小b這種結構么？ 因為只能是單方向的指引，所以應該是小b這種結構。兩個指針先后進入環里面，一個比另一個每次快一步，是不是一定會遇上。是的。那么如果快兩步呢？就是一個指針每次走3步，另一個每次走一步？相遇的話，快的那個是不是一定領先慢的那個若干個圈的長度？假設經過x步相遇，那么領先2x個節點。所以圈內節點數一定要是偶數才行？先想題目吧。
function linkedListWithCircle(head){
if(head==null||head.next==null) return false;
var fastNode = head;
var normalNode = head;
while(fastNode!=null&&fastNode.next!=null){//只是為了保證可以執行fastNode.next.next操作。避免null.next錯誤。
fastNode = fastNode.next.next;
normalNode = normalNode.next;
if(normalNode==fastNode) return true;
}
return false;
}
題目描述：判斷單鏈表是否有環，如果有，找到環的入口點
分析：由上題可知，按照 p2 每次兩步，p1 每次一步的方式走，發現 p2 和 p1 重合，確定了單向鏈表有環路了。接下來，讓 p2 回到鏈表的頭部，重新走，每次步長不是走 2 了，而是走 1，那么當 p1 和 p2 再次相遇的時候，就是在環路的入口點。加深思考。
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;
}
想畫個圖來著。還是算了吧。反正走了x步相遇，那么快的領先慢的x步，正好是一圈的長度。
假設從頭節點到圈的入口要走m步，那么慢節點在圈內走了x-m步，從相遇的節點到入口節點，差x-(x-m)=m步。
所以如果快節點從頭開始和慢節點以一樣的一格一格跑，必在入口處相遇。
還是畫個圖吧。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/90219.html
摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內功，...
摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內功，內功不行，就...
摘要：快速排序是不穩定的排序算法。瀏覽器的實現不同有什么影響排序算法不穩定有什么影響舉個例子某市的機動車牌照拍賣系統，最終中標的規則為按價格進行倒排序相同價格則按照競標順位即價格提交時間進行正排序。 本文要解決的問題 1、找出 Array.prototype.sort 使用的什么排序算法 2、用一種直觀的方式展示 Array.prototype.sort 的時間復雜度，看看它有多快？ 3、...
摘要：因為是在已經分組排序過的基礎上進行插入排序，所以效率高。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。形成左右兩個分區，再遞歸按之前的步驟排序。 算法復雜度 不是科班生的我，第一次看見時間復雜度之類的名詞表示很懵逼，所以就找了網上的資料補習了下： 時間復雜度：是指執行算法所需要的計算工作量 空間復雜度：是指算法在計算機內執行時所需存儲空間的度量 排序算法穩定性： 假定在待...
摘要：棧被稱為一種后入先出的數據結構。散列使用的數據結構叫做散列表。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。 前言 在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），...
閱讀 1864·2019-08-30 15:53
閱讀 3192·2019-08-30 15:44
閱讀 2805·2019-08-26 13:31
閱讀 1949·2019-08-26 12:10
閱讀 792·2019-08-26 11:01
閱讀 2120·2019-08-23 15:32
閱讀 1584·2019-08-23 13:43
閱讀 2529·2019-08-23 11:58
