資訊專欄INFORMATION COLUMN
摘要：繼續學習鏈表的算法鏈接題目描述刪除單鏈表倒數第個節點，，盡量在一次遍歷中完成。如果條件是，那么被刪除的點就是，但是這樣刪不掉。思路很相似，那么三分之一，四分之一，五分之一，或者均分三段，均分四段也是類似的想法。
繼續學習鏈表的算法鏈接
題目描述：刪除單鏈表倒數第 n 個節點，1 <= n <= length，盡量在一次遍歷中完成。
分析：看到題目時的第一想法是先遍歷一次計算出單鏈表的長度 length，然后在遍歷第二次刪除第 length - n + 1 個節點，但是這需要遍歷兩次。正常的刪除第 n 個節點只需要遍歷一次就可以，如何只遍歷一次找到倒數第 n 個節點呢？可以設置兩個指針 p1、p2，首先 p1 和 p2 都指向 head，p2 移動到第 n 個節點，然后 p1 和 p2 同時向后移動，當 p2 移動到末尾時，p1 剛好指向倒數第 n 個節點。因為最后要刪除倒數第 n 個節點，所以可以找到倒數第 n + 1 個節點，方便刪除節點。這種思想在學校的時候學習過，還是蠻有用的吧，還是可以學到很多東西的，只不過總是找了很多借口。
function Node(val){ //class的定義好像有點沒弄好
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個元素，就沒有倒數第n個元素
}
if(pointer2==null){ //總共就n個元素，那么head就是要刪除的那個點，返回下一個節點作為頭節點就好了。
return pointer1.next;
}
while(pointer2.next!=null){ //如果條件是pointer2!=null，那么被刪除的點就是pointer1，但是這樣刪不掉。所以應該記錄要刪除的節點的上一個節點。
pointer2=pointer2.next;
pointer1=pointer1.next;
}
pointer1.next = pointer1.next.next;//
return head;
}
我自己測試了下，測試用例如下，可能構建鏈表的過程有點傻。
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);
結果是 head 5 4 3 2 1 和 5 4 3 2 1
如果removeNthNodeFromEnd(head,7)，返回的是null。
showLinkedNode(head); var result = removeNthNodeFromEnd(head,3); showLinkedNode(result);
結果是head 5 4 2 1
還是得自己動手寫寫，可能以前能懂，但是過了一段時間以后就不懂了，讓往日的自己和后面的自己隔著時間對話。人并不總是在進步，每一個時間點的思考以及結論都很有意義。
類似的問題
題目描述：求單鏈表的中間節點，如果鏈表的長度為偶數，返回中間兩個節點的任意一個，若為奇數，則返回中間節點。
分析：這道題的思路和第 3 題「刪除單鏈表倒數第 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;
}
這個感覺比較簡單。
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70721.html
摘要：強烈推薦上值得前端學習的數據結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數據結構，提供進一步閱讀的解釋和鏈接。數據結構和算法必知必會的個代碼實現。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言 算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...
摘要：算法系列單源最短路徑算法迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。 Javascript算法系列 - 單源最短路徑 - Dijkstra算法 迪杰斯特拉算法是由荷蘭計算機科學家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有...
摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內功，...
摘要：實際上在這種將函數作為一等對象的語言里，策略模式已經融入到了語言本身當中，我們經常使用高階函數來封裝不同的行為，并且把它傳遞到另一個函數中。 聲明：這個系列為閱讀《JavaScript設計模式與開發實踐》 ----曾探@著一書的讀書筆記 1.策略模式的定義 將不變的部分和變化的部分隔開是每個設計模式的主題。 定義一系列的算法，把它們一個個封裝起來，并且使它們可以相互替換。 2.策略模式...
摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內功，內功不行，就...
摘要：中的算法附道面試常見算法題解決方法和思路關注每日一道面試題詳解面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程技能和文化契合度。值得記住的數組方法有和。一個好的解決方案是使用內置的方法。 JavaScript中的算法（附10道面試常見算法題解決方法和思路） 關注github每日一道面試題詳解 Introduction 面試過程通常從最初的電話面試開始，然后是現場面試，檢查編程...
閱讀 3142·2023-04-26 02:33
閱讀 3103·2023-04-25 21:33
閱讀 907·2021-09-02 09:56
閱讀 2910·2019-08-30 15:44
閱讀 2460·2019-08-30 13:15
閱讀 1035·2019-08-30 13:04
閱讀 1634·2019-08-29 15:09
閱讀 3957·2019-08-26 18:26
