資訊專欄INFORMATION COLUMN
摘要：思路查找倒數第個節點，可以看做是查找正序第個節點可以根據第一題的結果取數組的第個節點使用思路輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。
前言
??在寫項目的時候會發現，并沒有使用很多關于鏈表的東西，大多數情況使用的都是數組，但是由于在準備校招，很多公司都會考到這個問題，所以準備對鏈表的相關操作進行總結，并對其中的重難點進行強調，最后還會附加幾道關于鏈表的算法題，那么現在就開始吧！
鏈表的基礎操作 創建一個鏈表結構??了解過鏈表的同學應該都知道，鏈表有幾個特點：
可以動態擴展空間（在js中，數組也是這樣的，但是有的語言中數組的長度是固定的，不能動態添加，如c語言）
需要一個頭節點
需要知道下一個節點的地址
??可以將鏈表中的每個節點看成是一個對象，這個對象中有兩個屬性，一個是該節點的值，一個是該節點的下一個節點的地址（如果是雙鏈表，還要添加前一個節點地址的屬性）
function LinkedList(){
//輔助類：表示要加入鏈表的項
let node = function(element){
this.element = element;
this.next = null;//這個節點的下一個節點暫時為空
}
let length = 0;
let head = null;
this.append() = function(element){};//向鏈表的尾部添加節點
this.insert() = function(position,element){};//在指定的位置添加節點
this.remove = function(element){};//將指定的節點刪除掉
this.removeAt = function(position){};//將指定位置的節點刪除
this.searchElement = function(element){};//查找指定元素的位置
this.searchPosition = function(position){};//查找指定位置的元素
}
??上面代碼中包含了很多要實現的操作，包括最基本的增刪以及查詢。下面我們就來一一的實現上面列舉的方法：
實現增加節點的操作在尾節點處添加節點
function append(element){
let node = new Node(element);//1
let current;//2
//3
if(head === null){
head = node
}else{
current = head
while(current.next){
current = current.next
}
current.next = node
}
length++;//4
}
根據傳入的元素定義一個節點，該元素作為這個節點的值
定義一個變量表示當前的節點
判斷是否含有頭節點,如果沒有頭節點，說明鏈表中還沒有值，將傳進來的這個值作為頭節點；否則，對鏈表進行遍歷，找到最后一個節點，將其next屬性賦值為新增的節點
鏈表的長度+1
在任意位置添加節點
??將這個位置的前一個節點的next屬性賦值為這個節點，并將它原先的下一個節點保存下來，賦值給現在這個節點的next屬性
function insert(position,element){
if(position >=0 && position <= length){
//當position為length時，表示在尾節點處添加，包含了append方法
let node = new Node(element);
let current = head;
let previous;//當前節點的前一個節點，在position處添加節點，就是在previos和current之間添加
if(position = 0){
node.next = head;
head = node;
}else{
for(let i = 0;i< position;i++){
pervious = current;
current = current.next;
}
pervious.next = node;
node.next = current;
}
length++;
return true;
}else{
return false;
}
}
檢查postion是否越界,若沒有越界，則創建一個節點
定義一個變量表示當前的節點，初始化為頭節點，表示從頭節點開始遍歷；一個變量表示當前節點的前一個節點，作用是插入節點時方便找到前一個節點
判斷是否在頭節點前添加，如果是就將頭節點賦給node的next屬性，并且頭節點改為這個節點；否則，遍歷出這個位置的節點，將該節點插入到這個位置的節點前面
鏈表的長度+1
實現刪除節點的操作??基本思路：刪除節點的操作就是將目標節點前面的那個節點的指針指向目標節點的有一個節點
刪除指定節點
function removed(element){
let node = new Node(element);
let pervious;
let nextNode;
let current = head;
if(head != null){
while (current != node){
pervious = current;
current = current.next;
nextNode = current.next;
}
pervious.next = nextNode;
length--;
return true;
}else{
return false;
}
}
刪除指定位置的節點
function removedAt(position){
//判斷所給位置是否溢出
if(position > -1 && position < length){
let current = head;
let pervious;
let nextNode;
let i = 0;
while(i < position){
pervious = current;
current = current.next;
nextNode = current.next;
}
pervious.next = nextNode;
length--;
return true;
}else{
return false;
}
}
實現查詢節點的操作
??其實查詢節點和刪除節點差不多，都是通過遍歷，找到相應的節點或是相應的位置，然后進行操作，說起來比刪除節點還要簡單
查詢某個位置是哪個節點
function searchElement(element){
//輸入元素，找到該元素后返回該元素的位置
if(head != null){
let node = new Node(element);
let current;
let index = 0;
if(head == node){
return 0;
}else{
current = head;
while(current != node){
current = current.next;
index++;
}
return index;
}
}else{
return -1;
}
}
查詢某個節點是在哪個位置
function searchPosition(position){
//查找某一個位置的元素是什么
if(position > -1 && position < length){
let i = 0;
let current = head;
while(i< position){
current = current.next;
i++;
}
return current;
}else{
return null;
}
}
思路總結
??關于鏈表的操作還有很多，復雜一點的鏈表還有雙鏈表（在初始化節點的時候增加一個前節點）和循環鏈表（尾節點的下一個節點是頭節點），這些鏈表的操作也是可以使用js實現的，這里就不多說了。總結一下，鏈表的核心在于
鏈表中節點可看做一個對象，有兩個屬性值，一個是節點值，一個是指針
鏈表的增刪就是改變指針指向
鏈表查找時，重點是current = current.next
有關鏈表的算法題??這里總結幾道在?？途W上的劍指offer中刷到的幾道關于鏈表的算法題，這些題在筆試中還是很有可能遇到的，接著往下看吧！
1. 輸入一個鏈表，按鏈表值從尾到頭的順序返回一個ArrayList。
??思路：（1）將鏈表值從頭到尾輸出到一個數組中，然后將這個數組進行反轉得到ArrayList
????????（2）使用數組的unshift方法，將鏈表值倒序放進數組
????????（3）先使用棧存放順序遍歷的結果，利用棧先進后出的特性，出棧的時候用數組保存
//使用思路2的方法
function Node(element){
this.val = element
this.next = null
}
function logList(head){
if(head != null){
let ArrayList = [];
while(head){
ArrayList.unshift(head.element);
head = head.next;
}
return ArrayList;
}else{
return [];
}
}
2. 輸入一個鏈表，輸出該鏈表中倒數第k個結點。
??思路：（1）查找倒數第k個節點，可以看做是查找正序第length-k個節點
????????（2）可以根據第一題的結果取數組的第k-1個節點
//使用思路2
function Node(element){
this.element = element;
this.next = null;
}
function FindKthToTail(head, k)
{
let array = []
while(head != null){
array.unshift(head)
head = head.next;
}
return array[k-1];
}
3. 輸入一個鏈表，反轉鏈表后，輸出新鏈表的表頭。
??思路：把倒序后的鏈表放進一個數組中，然后將這個數組的每一位的next屬性指向下一位
function ListNode(x){
this.val = x;
this.next = null;
}
function ReverseList(pHead)
{
if(pHead){
let arr = [];
while(pHead){
arr.unshift(pHead);
pHead = pHead.next;
}
for(let i =0;i< arr.length;i++){
arr[i].next = arr[i+1]
}
return arr[0]
}
}
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/99257.html
摘要：網易跨境電商考拉海購在線筆試現場技術面面。如何看待校招面試招聘，對公司而言，是尋找勞動力對員工而言，是尋找未來的同事。 如何準備校招技術面試 標簽 ： 面試 [TOC] 2017 年互聯網校招已近尾聲，作為一個非 CS 專業的應屆生，零 ACM 經驗、零期刊論文發表，我通過自己的努力和準備，從找實習到校招一路運氣不錯，面試全部通過，謹以此文記錄我的校招感悟。 寫在前面 寫作動機 ...
摘要：前端面試總結先說背景，本人年月畢業，去年十月校招到今年月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含基礎，基礎，常見算法和數據結構，框架，計算機網絡相關知識，可能有的點很細，有的點很大，參考個人情況進行總結，方便對知識 前端面試總結 先說背景，本人2018年7月畢業，去年十月校招到今年10月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含： ...
摘要：前端面試總結先說背景，本人年月畢業，去年十月校招到今年月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含基礎，基礎，常見算法和數據結構，框架，計算機網絡相關知識，可能有的點很細，有的點很大，參考個人情況進行總結，方便對知識 前端面試總結 先說背景，本人2018年7月畢業，去年十月校招到今年10月一直在做前端開發工作，年前打算換工作，就重新梳理下面試考點總結包含： ...
摘要：而遍歷鏈表，則是跟著首元素一直遍歷至尾元素。單鏈表代碼實現類實現類用來設置鏈表的節點相關信息本節點信息指向下一個節點的指針類實現類實現的是一些對鏈表進行操作的方法，包括插入刪除節點查找節點等。 單鏈表初識 鏈表是由一組節點組合成的集合.每個節點都使用一個對象的引用指向它的后繼，指向另一個節點的引用叫做鏈 數組元素靠他們的位置進行引用，鏈表元素則是靠相互之間的關系進行引用，在下圖中bre...
閱讀 2395·2021-11-11 16:54
閱讀 1204·2021-09-22 15:23
閱讀 3645·2021-09-07 09:59
閱讀 1990·2021-09-02 15:41
閱讀 3283·2021-08-17 10:13
閱讀 3037·2019-08-30 15:53
閱讀 1235·2019-08-30 13:57
閱讀 1210·2019-08-29 15:16
