数据结构的存储方式只有两种：数组（顺序存储）和链表（链式存储）。

数组

  • 内存分配：连续存储，内存空间必须一次性分配够，数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；
  • 访问元素：通过索引快速找到对应元素，而且相对节约存储空间 O(1)。
  • 插入和删除元素，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

链表

  • 内存分配：因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；
  • 访问元素：因为存储空间不连续，查找一个节点或者访问特定编号的节点则需要 O(N)的时间
  • 删除元素：如果知道某一元素的前驱和后驱，操作指针即可删除该元素或者插入新元素，时间复杂度 O(1)。
  • 插入元素：由于不必须按顺序存储，链表在插入的时候可以达到 O(1)的复杂度
  • 空间：链表由于增加了结点的指针域，空间开销比较大。

参考：
1. 一文搞懂单链表的六大解题套路：https://labuladong.github.io/algo/1/6/

链表数据结构

链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
image.png

  1. class ListNode {
  2.   constructor(val, next) {
  3.     this.val = val; //节点的数据
  4.     this.next = next || null; //指针
  5.   }
  6. }
  8. class List {
  9.   constructor() {
  10.     this.head = new ListNode('head', null); //head节点初始next为null;
  11.   }
  12.   /* 在item后面插入新节点newEle */
  13.   insert(newEle, item) {
  14.     let newNode = new ListNode(newEle);
  15.     let cur = this.find(item);
  16.     newNode.next = cur.next;
  17.     cur.next = newNode;
  18.   }
  19.   find(item) {
  20.     let cur = this.head;
  21.     while (cur.val != item) {
  22.       cur = cur.next;
  23.     }
  24.     return cur;
  25.   }
  26.   findPre(item) {
  27.     let curNode = this.head;
  28.     while (curNode.next !== null && curNode.next.val != item) {
  29.       curNode = curNode.next;
  30.     }
  31.     return curNode;
  32.   }
  33.   remove(item) {
  34.     let preNode = this.findPre(item);
  35.     if (preNode.next !== null) {
  36.       preNode.next = preNode.next.next;
  37.     }
  38.   }
  39. }
  40. var l = new List();
  41. l.insert('songyuan', 'head');
  42. l.insert('changchun', 'songyuan');
  43. l.insert('beijing', 'changchun');
  44. console.log(111, l);

解题套路

https://labuladong.github.io/algo/1/6/

  1. 技巧1： 「虚拟头结点」技巧，也就是 dummy 节点
  2. 技巧2： 快慢指针 环形链表
  3. 技巧3： 双指针移动找到倒数第K个节点

    力扣练习

    234. 回文链表

    给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
    image.png

思路：
https://labuladong.github.io/algo/2/15/17/

解法1：那么最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。关于如何反转链表，可以参见前文 递归翻转链表的一部分。

解法2：借助二叉树 [后序遍历] 的思路，不需要显式反转原始链表也可以倒序遍历链表。链表兼具递归结构，树结构不过是链表的衍生。那么，链表其实也可以有前序遍历和后序遍历

解法3： 1. 快慢指针找到链表中点 2.如果fast指针没有指向null，长度为奇数，slow前进 3.从slow开始反转后面的链表，计算回文。算法总体的时间复杂度 O(N)，空间复杂度 O(1)，已经是最优
image.png
image.png
image.png

var isPalindrome = function(head) {
    let fast = head;
    let slow = head;
    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;
    }
    //此时slow指向链表中点 fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：
    if(fast!==null){
        slow = slow.next;
    }
    //开始反转
    left = head;
    right = reverseList(slow);

    while(right!==null){
        if(left.val !== right.val){
            return false;
        }
        left = left.next;
        right = right.next;
    }
    return true;
};

var reverseList = function(head) {
    if(head === null || head.next === null){
        return head;
    }
    var new_head = null;//指向新链表头结点的指针
    while(head){
        var next = head.next;//备份head.next
        head.next = new_head;//更新head.next
        new_head=head;   //移动new_head
        head=next;//遍历链表

    }
    return new_head;//返回新链表的头结点
};

21. 合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

image.png
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路：dummy节点

//    l1            l2
//   1-4-6         0-5-7
// 较小的节点插入到p节点后
//     dummy  
//      0   -> 0 ->1
//      pre    pre pre

var mergeTwoLists = function(l1, l2) {

    var dummy=new ListNode(0);  //设置临时头结点      
    var pre=dummy;    

    while(l1&&l2){//l1 l2不同时为空
       if(l1.val>l2.val){
            p.next=l2;
            l2=l2.next;
            p=p.next;
       }else{
           p.next=l1;
           l1=l1.next;
           p=p.next;
       }
    }
    // l1有剩余
    if(l1){
        p.next=l1;
    }
    // l2有剩余
    if(l2){
        p.next=l2;
    }  
    return dummy.next  
};

image.png

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

思路：
解法1：合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？
这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点

解法2： 二分法

19.删除链表中倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

思路：
解法1：两遍循环，第一次找到链表的长度n，第二次从头开始移动n-k，就是倒数第k个节点
解法2：利用技巧3，两个指针p1,p2, p1向前走k步，剩余n-k,这时p2再从头向后跟随p1往后移动，直到p1挪到链表尾部，这时p2的节点就是倒数第k个节点

要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用

//从链表中找到倒数第k个节点
var findFromEnd = function(head,k){
    var p1 = new ListNode();
    var p2 = new ListNode();
    p1.next = head;
    p2.next = head;
     // p1 先走 k 步
    for (var i = 0; i < k; i++) {
        p1 = p1.next;
    }
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k 个节点
    return p2;
}

var removeNthFromEnd = function(head, n) {
     // 虚拟头结点
    var dummy = new ListNode(-1);
    dummy.next = head;
   // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    var x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
};

876. 链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

思路：

问题的关键也在于我们无法直接得到单链表的长度 n，常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。

如果想一次遍历就得到中间节点，也需要耍点小聪明，使用「快慢指针」的技巧：
我们让两个指针 slow 和 fast 分别指向链表头结点 head。
每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

* @param {ListNode} head
 * @return {ListNode}
 */

var middleNode = function(head) {
     // 快慢指针初始化指向 head
    var fast = new ListNode();
    var low = new ListNode();
    fast.next = head;
    low.next = head;
    // 快指针走到末尾时停止
    while (fast != null && fast.next != null) {
        // 慢指针走一步，快指针走两步
        low = low.next;
        fast = fast.next.next;
    };

        // fast != null 时总共有奇数个结点, 直接返回中间结点low
        // fast == null 时总共有偶数个结点, 返回右边的中间结点low.next
        return fast  ? low.next : low;
};

141.环形链表

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
image.png

image.png
思路：
每当慢指针 slow 前进一步，快指针 fast 就前进两步。
如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

var hasCycle = function(head) {
    if(!head) return false;
    var faster = head;
    var slower = head;
    while (faster && faster.next) {
        faster = faster.next.next;
        slower = slower.next;
        if (slower === faster) return true;
    }
    return false;
};

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
image.png
思路：
image.png

慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步
image.png
fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走k步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：
image.png
只要我们把快慢指针中的任一个重新指向 head，然后两个指针同速前进，k - m 步后一定会相遇，相遇之处就是环的起点了。

也就是slow从head出发 fast相同速度从meet出发，一定会在start相遇

var detectCycle = function(head) {
           if (!head || !head.next) {
        return null;
      }
      let slow = head.next;
      let fast = head.next.next;
      // 1.判断是否有环 如果是停留在meet处
      while (slow != fast) {
        if (fast === null || fast.next === null) {
          return null;
        }
        slow = slow.next;
        fast = fast.next.next;
      }
      // 2.获取环的长度
      let temp = slow;
      let length = 1;
      slow = slow.next;
      while (temp != slow) {
        slow = slow.next;
        length++;
      }
      // 3.找公共节点
      slow = fast = head;
       // fast指针移动到meet处
      while (length-- > 0) {
        fast = fast.next;
      }
       // fast从meet开始走  slow从head开始走 最终相等的地方就是环开始节点
      while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow;  
};

160. 相交链表

编写一个程序，找到两个单链表相交的起始节点。
如下面的两个链表：

// A:          a1 → a2
//                    ↘
//                      c1 → c2 → c3
//                    ↗            
// B:     b1 → b2 → b3

思路：
1. hashSet： HashSet 记录一个链表的所有节点，然后和另一条链表对比，但这就需要额外的空间

  1. 双指针

image.png

在节点 c1 开始相交。
如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1。
所以，解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1：
image.png

var getIntersectionNode = function(headA, headB) {
    var pA = headA;
    var pB = headB;
    while(pA !== pB){
        pB = pB? pB.next: headA;
        pA = pA? pA.next: headB;
    }
    return pA;
};

206. 反转链表

参考 https://labuladong.github.io/algo/2/15/15/
反转一个单链表。
示例:

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

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

//    head   
//      1  - 2  -3  -4   -5 -null
//          next
//                       1  -> null
//                      new_head
var reverseList = function(head) {
    if(head === null || head.next === null){
        return head;
    }
    var new_head = null;//指向新链表头结点的指针
    while(head){
        var next = head.next;//备份head.next
        head.next = new_head;//更新head.next
        new_head=head;   //移动new_head
        head=next;//遍历链表

    }
    return new_head;//返回新链表的头结点
};

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

//       modify_list_tail
//           |
//      1-   2-3-4  -5-null
//      /    \
//pre—head  head
//
// 1：找到逆转的开始节点 head,也是逆转后的尾节点，记录该节点的前驱pre—head
// 2：逆转区间开始逆转，逆转后的区间链表new—head
// 3: 连接两端
var reverseBetween = function(head, m, n) {
    var change_len = n-m+1;//计算需要逆转的节点数
    var pre_head = null;//初始化开始倒序的节点的前驱
    var  result = head  ;//倒序后链表的头结点


    while(head && --m){  //将head向后移动m-1个位置，找到开始倒序的位置
        pre_head = head;
        head = head.next;
    }
    var modify_list_tail = head;//将modify_list_tail指向当前head，即倒序后的链表尾
    var new_head = null;
    while(change_len && head){
        var next = head.next;
        head.next = new_head;
        new_head = head;
        head = next;
        change_len --;

    }

    modify_list_tail.next = head;//连接倒序后的最后一个节点和后继
    if(pre_head){
        pre_head.next = new_head;//连接前驱和倒序后的第一个节点
    } else {
        result = new_head;//从第一个节点开始倒序，返回倒序后的头结点
    }

    return result
};


237.删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点

示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

var deleteNode = function(node) {
    if(node===null) return;
    node.val = node.next.val;
    node.next = node.next.next;  
};

203. 移除链表元素

删除链表中等于给定值 val 的所有节点。

示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

var removeElements = function(head, val) {
    var dummy = new ListNode(0);
    dummy.next = head; //链接临时头结点
    var pre  = dummy;
    var cur = head;

    while(cur !== null){
        if(cur.val === val){
            pre.next = cur.next;
            cur = pre.next
        } else {
            pre = cur;
            cur = cur.next
        }
    }
    return dummy.next;   
};


83. 删除排序链表中的重复元素


给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    if(head==null || head.next ==null) return head;
    var cur = head
    while(cur.next != null){
        if(cur.next.val == cur.val){
            cur.next = cur.next.next
        } else {
            cur = cur.next
        }
    }
    return head
};

82. 删除排序链表中的重复元素 II


给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
参考：https://www.youtube.com/watch?v=1I82s08OE0c&t=415s

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// real pre dummy cur
// 0   1-2-3-3-4-4-5
// 0-1 2-3-4-4-5
var deleteDuplicates = function(head) {
    if(head ==null) return null;
    var dummy = new ListNode(0);
    var pre = dummy;
    var cur = head;
    var real = dummy; //返回的真正链表

    while(cur != null){
        if((pre==dummy || pre.val !=cur.val) && (cur.next == null || cur.next.val != cur.val)){
            real.next = cur;//链接链表节点
            real = cur;
        }
        pre = cur;
        cur = cur.next;
        pre.next = null;//断开pre和cur的节点链接
    }

    return  dummy.next

};