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

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

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

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

需要一個(gè)頭節(jié)點(diǎn)

需要知道下一個(gè)節(jié)點(diǎn)的地址

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

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

      let length = 0;
      let head = null;

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

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

在尾節(jié)點(diǎn)處添加節(jié)點(diǎn)

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ù)傳入的元素定義一個(gè)節(jié)點(diǎn)，該元素作為這個(gè)節(jié)點(diǎn)的值

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

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

鏈表的長度+1

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

分析：

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

    function insert(position,element){
      if(position >=0 && position <= length){
        //當(dāng)position為length時(shí)，表示在尾節(jié)點(diǎn)處添加，包含了append方法
        let node = new Node(element);
        let current = head;
        let previous;//當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，在position處添加節(jié)點(diǎn)，就是在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)建一個(gè)節(jié)點(diǎn)

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

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

鏈表的長度+1

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

刪除指定節(jié)點(diǎn)

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

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

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

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

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

查詢某個(gè)位置是哪個(gè)節(jié)點(diǎn)

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

查詢某個(gè)節(jié)點(diǎn)是在哪個(gè)位置

function searchPosition(position){
      //查找某一個(gè)位置的元素是什么
      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ù)雜一點(diǎn)的鏈表還有雙鏈表（在初始化節(jié)點(diǎn)的時(shí)候增加一個(gè)前節(jié)點(diǎn)）和循環(huán)鏈表（尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是頭節(jié)點(diǎn)），這些鏈表的操作也是可以使用js實(shí)現(xiàn)的，這里就不多說了?？偨Y(jié)一下，鏈表的核心在于

鏈表中節(jié)點(diǎn)可看做一個(gè)對(duì)象，有兩個(gè)屬性值，一個(gè)是節(jié)點(diǎn)值，一個(gè)是指針

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

鏈表查找時(shí)，重點(diǎn)是current = current.next

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

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

??思路：（1）將鏈表值從頭到尾輸出到一個(gè)數(shù)組中，然后將這個(gè)數(shù)組進(jìn)行反轉(zhuǎn)得到ArrayList
????????（2）使用數(shù)組的unshift方法，將鏈表值倒序放進(jìn)數(shù)組
????????（3）先使用棧存放順序遍歷的結(jié)果，利用棧先進(jìn)后出的特性，出棧的時(shí)候用數(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. 輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。

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

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

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

????本人的水平不佳，可能有些地方寫錯(cuò)了，歡迎在評(píng)論中指出，大家一起進(jìn)步喲！