摘要：思路查找倒數(shù)第個節(jié)點，可以看做是查找正序第個節(jié)點可以根據(jù)第一題的結(jié)果取數(shù)組的第個節(jié)點使用思路輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。

??在寫項目的時候會發(fā)現(xiàn)，并沒有使用很多關(guān)于鏈表的東西，大多數(shù)情況使用的都是數(shù)組，但是由于在準(zhǔn)備校招，很多公司都會考到這個問題，所以準(zhǔn)備對鏈表的相關(guān)操作進行總結(jié)，并對其中的重難點進行強調(diào)，最后還會附加幾道關(guān)于鏈表的算法題，那么現(xiàn)在就開始吧！

??了解過鏈表的同學(xué)應(yīng)該都知道，鏈表有幾個特點：

可以動態(tài)擴展空間（在js中，數(shù)組也是這樣的，但是有的語言中數(shù)組的長度是固定的，不能動態(tài)添加，如c語言）

需要一個頭節(jié)點

需要知道下一個節(jié)點的地址

??可以將鏈表中的每個節(jié)點看成是一個對象，這個對象中有兩個屬性，一個是該節(jié)點的值，一個是該節(jié)點的下一個節(jié)點的地址（如果是雙鏈表，還要添加前一個節(jié)點地址的屬性）

function LinkedList(){
      //輔助類：表示要加入鏈表的項
      let node = function(element){
        this.element = element;
        this.next = null;//這個節(jié)點的下一個節(jié)點暫時為空
      }

      let length = 0;
      let head = null;

      this.append() = function(element){};//向鏈表的尾部添加節(jié)點
      this.insert() = function(position,element){};//在指定的位置添加節(jié)點
      this.remove = function(element){};//將指定的節(jié)點刪除掉
      this.removeAt = function(position){};//將指定位置的節(jié)點刪除
      this.searchElement = function(element){};//查找指定元素的位置
      this.searchPosition = function(position){};//查找指定位置的元素
    }

??上面代碼中包含了很多要實現(xiàn)的操作，包括最基本的增刪以及查詢。下面我們就來一一的實現(xiàn)上面列舉的方法：

在尾節(jié)點處添加節(jié)點

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
    }

代碼分析：

根據(jù)傳入的元素定義一個節(jié)點，該元素作為這個節(jié)點的值

定義一個變量表示當(dāng)前的節(jié)點

判斷是否含有頭節(jié)點,如果沒有頭節(jié)點，說明鏈表中還沒有值，將傳進來的這個值作為頭節(jié)點；否則，對鏈表進行遍歷，找到最后一個節(jié)點，將其next屬性賦值為新增的節(jié)點

鏈表的長度+1

在任意位置添加節(jié)點

分析：

??將這個位置的前一個節(jié)點的next屬性賦值為這個節(jié)點，并將它原先的下一個節(jié)點保存下來，賦值給現(xiàn)在這個節(jié)點的next屬性

    function insert(position,element){
      if(position >=0 && position <= length){
        //當(dāng)position為length時，表示在尾節(jié)點處添加，包含了append方法
        let node = new Node(element);
        let current = head;
        let previous;//當(dāng)前節(jié)點的前一個節(jié)點，在position處添加節(jié)點，就是在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是否越界,若沒有越界，則創(chuàng)建一個節(jié)點

定義一個變量表示當(dāng)前的節(jié)點，初始化為頭節(jié)點，表示從頭節(jié)點開始遍歷；一個變量表示當(dāng)前節(jié)點的前一個節(jié)點，作用是插入節(jié)點時方便找到前一個節(jié)點

判斷是否在頭節(jié)點前添加，如果是就將頭節(jié)點賦給node的next屬性，并且頭節(jié)點改為這個節(jié)點；否則，遍歷出這個位置的節(jié)點，將該節(jié)點插入到這個位置的節(jié)點前面

鏈表的長度+1

??基本思路：刪除節(jié)點的操作就是將目標(biāo)節(jié)點前面的那個節(jié)點的指針指向目標(biāo)節(jié)點的有一個節(jié)點

刪除指定節(jié)點

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

代碼分析：重點在于抓住需要哪些節(jié)點，并且進行這個操作需要改變什么，判斷條件是怎樣的

刪除指定位置的節(jié)點

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

??其實查詢節(jié)點和刪除節(jié)點差不多，都是通過遍歷，找到相應(yīng)的節(jié)點或是相應(yīng)的位置，然后進行操作，說起來比刪除節(jié)點還要簡單

查詢某個位置是哪個節(jié)點

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

查詢某個節(jié)點是在哪個位置

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

??關(guān)于鏈表的操作還有很多，復(fù)雜一點的鏈表還有雙鏈表（在初始化節(jié)點的時候增加一個前節(jié)點）和循環(huán)鏈表（尾節(jié)點的下一個節(jié)點是頭節(jié)點），這些鏈表的操作也是可以使用js實現(xiàn)的，這里就不多說了?？偨Y(jié)一下，鏈表的核心在于

鏈表中節(jié)點可看做一個對象，有兩個屬性值，一個是節(jié)點值，一個是指針

鏈表的增刪就是改變指針指向

鏈表查找時，重點是current = current.next

??這里總結(jié)幾道在牛客網(wǎng)上的劍指offer中刷到的幾道關(guān)于鏈表的算法題，這些題在筆試中還是很有可能遇到的，接著往下看吧！

1. 輸入一個鏈表，按鏈表值從尾到頭的順序返回一個ArrayList。

??思路：（1）將鏈表值從頭到尾輸出到一個數(shù)組中，然后將這個數(shù)組進行反轉(zhuǎn)得到ArrayList
????????（2）使用數(shù)組的unshift方法，將鏈表值倒序放進數(shù)組
????????（3）先使用棧存放順序遍歷的結(jié)果，利用棧先進后出的特性，出棧的時候用數(shù)組保存

//使用思路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. 輸入一個鏈表，輸出該鏈表中倒數(shù)第k個結(jié)點。

??思路：（1）查找倒數(shù)第k個節(jié)點，可以看做是查找正序第length-k個節(jié)點
????????（2）可以根據(jù)第一題的結(jié)果取數(shù)組的第k-1個節(jié)點

//使用思路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. 輸入一個鏈表，反轉(zhuǎn)鏈表后，輸出新鏈表的表頭。

??思路：把倒序后的鏈表放進一個數(shù)組中，然后將這個數(shù)組的每一位的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]
    }
}

????本人的水平不佳，可能有些地方寫錯了，歡迎在評論中指出，大家一起進步喲！