前端程式員學好演算法系列（三）鏈表

接下來我們來看鏈表題

206. 反轉鏈表
反轉一個單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

解題：
鏈表題需要我們設立更多的指針來保存我們當前操作的細節；
1.我們需要定義3個指針 pre，cur ，next，pre為當前鏈表的前一個節點預設為空，cur為鏈表的第一個指針， 下一個指針next 為 cur.next 因為有可能存在越界所以我們在存在cur的時候再去取next指針；
2.我們把next指針指向pre，pre指向當前cur指針，當前指針指向暫存的next，最後我們返回pre指針；

var reverseList = function(head) {

   let pre = null
   let cur = head
   let next = null
   while(cur!=null){
       next = cur.next
       // 將當前節點指向pre
       cur.next = pre
       pre = cur
       cur = next
   }
   return pre

};

203. 移除鏈表元素
刪除鏈表中等於給定值 val 的所有節點。

示例:

輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

解題：
1.當前刪除邏輯如上圖，但需要註意的是我們刪除鏈表第一個節點時，是不適用的,所以我們一般採用增加虛擬頭節點的方式，

2.鏈表問題的令一個重要思想是明白js對象是引用類型  let a = {name: '1'} let b = a 時，修改b的屬性（註意不是本身）時，數據a的值也會發生改變

let a = {name:1}
let b = a
b.name = 2
console.log(a) //輸出 {name: 2}

3.我們迴圈cur.next的下一個指針 如果cur.next.val==val時，我們把cur.next = cur.next.next,最後返回list.next

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
     let list = new ListNode(-1)
     list.next = head
     let cur = list
     while(cur.next!==null){
         if(cur.next.val==val){
            cur.next = cur.next.next
         }else {
            cur = cur.next
         }
     }
     return list.next
};