题目一览图

链表相关 - 图1

零、链表概述

【链表的定义】
【链表】是基本的数据结构。链表由若干个节点组成，每个节点包括数据 val 和指向下一个节点的指针 next 。

  1. struct ListNode{
  2.     int val;
  3.     ListNode *next;
  4.     ListNode( int x ) : val(x),next(Null){}
  5. }
  1. function ListNode(val,next){
  2.     this.val = val===undefined? 0:val;
  3.   this.next = next===undefined? null:next;
  4. }

【链表的分类】
【单链表】单链表入口是头结点 head ，每个节点只能指向下一个节点。
image.png
【双链表】双链表的优势是可以从两个方向进行查询，每个节点有两个指针域，分别是指向前一个指针的 prev ，另一个是指向后一个节点的 tail 。
image.png
【循环链表】循环链表就是单链表头尾相连的结果。
image.png
【链表的操作】
【遍历】设置索引 p ，初始值为 head ，然后不停遍历直至 p 节点为空。

let p = head;
while(end) p = p.next;

【删除】比如要删除 cur 节点，我们需要知道 cur 前一个节点 pre ，让 pre 连接 cur.next 指向的节点。
image.png

prev.next = prev.next.next;

【添加】主要涉及指针的重新连接，具体流程如下：
image.png

preNode.next = newNode , newNode.next = nextNode;


【链表的优势】
链表的定义和操作可以看出，链表没有固定的存储位置，没有固定的长度，并且增删操作都是 O(1) ，时间复杂度较小。适用于数据量不固定，增删频繁的操作**。

一、穿针引线

类型概述

【链表】最主要考察的就是链表的基本操作，所谓【穿针引线】不过是描述指针断开、重连的一个过程。本节将分为三个部分：

  • 【基本操作】主要涉及与链表的【增加】【删除】相关的基本题目。
    • 在本部分有个重要的技巧，即【虚拟头结点】，由于链表增删都需要前一个节点，为了避免每次头节点 head 都要单独处理，所以在头结点前再加个【虚拟头结点】解决这个问题。本文将该【虚拟头结点】称为【哑结点】。
  • 【递归/迭代操作】以【反转链表】为起始，讲述如何处理链表的递归问题。这一类题的特征是具有重复操作，所以可以用递归函数进行化简。
  • 【链表重组】主要是总结需要将【链表】按照一定规则拆成两个链表，再进行合并的题目。

题型一 | 基本操作

题型串联

1 移除链表元素

【概述】穿针引线 删除
【题目描述**】
删除链表中等于给定值 val 的所有节点。
【题目示例**】

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

【题目分析**】
本题要求删除特定值的元素。可知本题考查链表的【删除】操作，按照一般思路是：遍历得到传入元素的前一元素，然后进行删除。为了不单独判定头节点 head ，需要添加【哑结点】**进行辅助。

var removeElements = function(head, val) {
    const dummy = new ListNode(-1);
    dummy.next = head;

    let cur = dummy;
    while(cur.next){
        if( val === cur.next.val) cur.next = cur.next.next;
        else cur = cur.next;
    }
    return dummy.next;
};

2 删除链表中的节点

【概述】穿针引线 删除
【题目描述**】
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。
【题目示例**】

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

【题目分析**】
本题要求删除传入的元素。可知本题考查链表的【删除】操作，按照一般思路是：遍历得到传入元素的前一元素，然后进行删除。但是本题的特殊之处是：传入的是节点且在非末尾位置，所以我们可以转换下思路，将题目变成【删除传入元素的下一个元素，然后取而代之】**，这样就可以省去遍历操作。
image.png

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

4 设计链表

【概述】穿针引线 增删
【题目描述**】**
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

【题目示例**】**

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

【题目分析**】**
本题要求实现链表的基本操作。主要考察基本增删的基本操作，唯一注意的是需要添加长度属性，判断输入的索引是否越界。
【构造类】

function ListNode(val,next){
    this.val = val === undefined ? 0 : val ;
    this.next = next === undefined ? null:next;
}

var MyLinkedList = function() {
    this.dummy = new ListNode(-1);
    this.length = 0;
};

【获取节点】

MyLinkedList.prototype.get = function(index) {
    if( index > this.length-1 || index < 0 ) return -1;
    let cur = this.dummy.next;
    while(index--) cur = cur.next;
    return cur.val;
};

【头尾添加】

MyLinkedList.prototype.addAtHead = function(val) {
    const tmp = new ListNode(val);
    tmp.next = this.dummy.next , this.dummy.next = tmp;
    this.length++;
};

MyLinkedList.prototype.addAtTail = function(val) {
    const tmp = new ListNode(val);
    let cur = this.dummy;
    while(cur.next) cur=cur.next;
    cur.next=tmp;
    this.length++;
};

【指定位置增删】

MyLinkedList.prototype.addAtIndex = function(index, val) {
    if(index>this.length) return;
    const tmp = new ListNode(val);
    let cur = this.dummy;
    while(index--)cur=cur.next;
    tmp.next = cur.next , cur.next = tmp;
    this.length++;
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
    if(index>=this.length||index<0)return;
    let cur = this.dummy;
    while(index--)cur=cur.next;
    cur.next = cur.next.next;
    this.length--;
};

3 对链表进行插入排序

【概述】穿针引线 排序 增删操作
【题目描述**】
对链表进行插入排序。
【题目示例**】

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

【题目分析**】
本题要求对链表进行插入排序。首先要了解【插入排序】**的过程，首先要找到不符合递增顺序的节点，然后将其拿出放在最前面，对应链表变成如下几个操作：

  1. 【遍历】遍历元素，看各节点是否满足递增顺序，cur.val <= cur.next.val 。
  2. 【删除】如遇到不满足递增的节点，先将其在链表中删除，cur.next = cur.next.next 。
  3. 【增加】放至头部相应位置。

【逻辑分析**】**

  1. 因为可能涉及在头部添加和删除操作，我们先设置【哑结点】dummy 。
  2. 我们采用指针 cur 遍历链表，它从 head 节点开始，每次对比 cur 和 cur.next 。为了确保两者都有值，所以我们 while 循环的条件是 cur && cur.next 。
  3. 如果不满足 cur.val <= cur.next.val ，说明遇到该转移的点了。
    1. 第一步，获取它，const tmp = cur.next 。
    2. 第二步，删除它，原点删除节点 ，cur.next = cur.next.next 。
    3. 第三步，转移它，我们先要找到插入的位置，再插入节点。
      1. 寻找插入点前一个位置，索引指针 fromHead 从 dummy 开始，找到第一个大于转移节点 tmp 的前一个位置。
      2. 然后转移节点 tmp 连接 索引指针 fromHead 后一个，然后索引指针 fromHead 再连接 tmp 。
  4. 返回【哑结点】dummy 下一指针，即为所求。
    var insertionSortList = function(head) {
if( !head ) return null;
const dummy = new ListNode(-1,head);
let cur = head;
while( cur && cur.next ) {
  if( cur.val <= cur.next.val ) {
      cur = cur.next;
      continue;
  }
  const tmp = cur.next;
  cur.next = cur.next.next;
  let fromHead = dummy;
  while( fromHead!==cur && fromHead.next.val <= tmp.val ) fromHead = fromHead.next;
  tmp.next = fromHead.next;
  fromHead.next = tmp;
}
return dummy.next;
};

题型二 | 递归/迭代法

题型串联

1 反转链表

【概述】穿针引线 递归
【题目描述**】
反转一个单链表。
【题目示例**】

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

【题目分析**】**
本题要求翻转整个链表。由于翻转链表是一个个翻转的，子操作具有重复性，可以使用递归处理。

  • 【递归函数】我们假设递归函数为 reverse(head) 。
    • 定义为翻转以 head 为开头的链表，并返回反转后的头结点。
    • 当传入是 head 时，我们会将 head.next 交给递归函数 reverse(head.next) ，得到翻转后链表和它的头节点 last 。
    • 这时将 head 节点也连接起来。head 要连接在翻转后链表的尾部，也就是 head.next.next 。
    • 最后让 head 连接空节点，遍完成翻转操作。

image.png**

var reverseList = function(head) {
    if(!head) return null;
    const reverse = (head)=>{
        if(head.next===null) return head;
        const last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
    return reverse(head);
};

2 反转链表 II

【概述】穿针引线 递归
【题目描述**】
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
【题目示例**】

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

【题目分析**】
本题要求翻转部分链表。由于两头都有限制，所以我们先从翻转 1 到 n 的链表开始分析。
【翻转 1 到 n 的链表】**
与【翻转完整链表】唯一的区别是需要用全局的指针 p 记录翻转子链表后续的节点。
image.png
然后我们再处理前面 m 的限制。首先 m===1 的时候，可以直接采用上面的方法进行翻转，那不等于 1 的时候那？我依旧可以用递归解决，如果 head 视为链表开头，就是从第 m 个节点开始翻转；那如果 head.next 视作开头，开始的节点就是 m-1 了。以此类推，终会递归到 m===1 的那一时刻，我们就可以直接采用【翻转 1 到 n 的链表】的方法了。

var reverseBetween = function(head, m, n) {
    let p = null;
    const reverseN = (head,n)=>{
        if( n === 1 ){
            p = head.next;
            return head;
        }
        const last = reverseN(head.next,n-1);
        head.next.next = head;
        head.next = p;
        return last;
    };
    if(m===1){
        return reverseN(head,n)
    }
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
};

3 两两交换链表中的节点

【概述】穿针引线
【题目描述**】
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换
【题目示例**】

输入：head = [1,2,3,4]
输出：[2,1,4,3]

【题目分析】
本题要求以两个一组进行翻转。稍微观察，能看出本题具有相同的操作，即每次翻转 **2** 长的链表。于是设置递归函数 swapPairs(head) 实现 head 为头，以 2 一组翻转链表。假设head.next 为 p ，两两交换只需要 p.next=head ，然后让 head 直接连接后续翻转好的链表 swapPairs(p.next) 。
image.png

var swapPairs = function(head) {
  if( !head || !head.next ) return head;

    const p = head.next;
    head.next = swapPairs(p.next);
    p.next = head;
    return p;
};

4 K 个一组翻转链表

【概述】穿针引线 递归
【题目描述**】
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
【题目示例**】

输入: 1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

【题目分析**】
本题要求以K个一组进行翻转。本题也具有相同的操作，即每次翻转 k 长的链表**。于是设置递归函数 reverseKGroup(head,k) 实现 head 为头，以 K 一组翻转链表。假设head 后 K 个节点为 p ，每次函数只处理 head 到 p 前这一段的链表，后面的翻转交给 reverseKGroup(p,k) 。接下来谈论一些细节问题：

  • 如何实现翻转？可参考【翻转链表 II】，但是作为一个子函数没必要写的这么复杂，使用迭代也可以处理问题。由于这是翻转一个区域的链表，我们设翻转函数为 reverse(head,end) ，具体过程与下图所示。

image.png

  • 如递归？详见【两两交换链表中的节点】，递归思路一致。 ```javascript const reverse = (head,end)=>{ let pre = next = null; while (head != end) { next = head.next; head.next = pre; pre = head; head = next; } return pre; }

var reverseKGroup = function(head, k) { if( !head || !head.next ) return head; let tail = head; for (let i = 0; i < k ; i++) { if (!tail) return head; tail = tail.next; } const res = reverse(head, tail); head.next = reverseKGroup(tail,k); return res; };

<a name="WkenH"></a>
#### 5 [旋转链表](https://leetcode-cn.com/problems/rotate-list/)
**【概述】穿针引线 合并**<br />**【题目描述****】**<br />给定一个链表，旋转链表，将链表每个节点向右移动 `k` 个位置，其中 `k` 是非负数。<br />**【题目示例****】**

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

**【题目分析****】**<br />本题要求让链表右移动 k 个位置。通过分析发现，移动后的链表具有以下特征：<br />

   1. 链表的尾部将会和链表的头部相连接。
   1. 第 `len - k + 1` 节点将会成为新的头部。

所以我们要做的是：

   1. **【得到尾结点 end】**直接遍历到结尾即可，顺便得到长度 `len` 。
   1. 【**得到 `len - k + 1` 节点 p**】得到长度后，直接遍历即可。
   1. **【end】-【head】，【head】替换为【p.next】, 【p】- null**

**【逻辑分析****】**

   1. 因为可能涉及替换头部操作，我们先设置**【哑结点】**`dummy` 。
   1. 用指针 `end` 遍历链表，得到最后一个节点和链表长度 `len` 。
   1. 由于 `k` 可能超出链表范围，所以进行除余 `k = k%len` 。
   1. 指针 `p` 从 `dummy` 右移 `len-k` 得到 `len - k + 1` 节点。
   1. 按照下图**【穿针引线】**，最后返回**【哑结点】**`dummy` 下一指针，即为所求。

![image.png](https://cdn.nlark.com/yuque/0/2021/png/8415624/1610180973073-ea0c3aa5-879e-4e4c-90e5-c0f84f4ac00c.png#align=left&display=inline&height=287&margin=%5Bobject%20Object%5D&name=image.png&originHeight=574&originWidth=656&size=31666&status=done&style=none&width=328)
```javascript
var rotateRight = function(head, k) {
    const dummy = new ListNode(-1,head);
    let len = 0 , end = dummy;
    while(end.next) len++,end = end.next;
    k = k % len;
    let p = dummy ;
    for( let i = 0 ; i < len - k ; i++,p = p.next);
    end.next = dummy.next;
    dummy.next = p.next;
    p.next = null;
    return dummy.next;
};

题型三 | 重组链表

题型串联

1 合并两个有序链表

【概述】穿针引线 合并
【题目描述**】
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
【题目示例**】

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

【题目分析**】
本题要求合并两个链表。思路比较简单，就是新建一个空的哑结点，两个链表较大的节点依次连接到新链上。
【逻辑分析**】

  1. 创建【哑结点】dummy 作为合并后链表的开头，并用 指针 p 来定位合并后链表当前位置。
  2. 遍历两个升序链表 l1 l2 ，将较大值接到指针 p 后，具有较大值的链表和 指针 p 后移一步。
  3. 如果两个升序链表 l1 l2 有其一没有遍历到最后，说明该剩下部分都是小于另外一个链表，可以直接接到输出链表的尾部。

  4. 返回【哑结点】dummy 下一指针，即为所求。

    var mergeTwoLists = function(l1, l2) {
const dummy = new ListNode();
let p = dummy;

while(l1 && l2){
  if(l1.val < l2.val){
      p = p.next = l1;
      l1 = l1.next;
  }else{
      p = p.next = l2;
      l2 = l2.next;
  }
}
if(l1) p.next = l1;
if(l2) p.next = l2;

return dummy.next;
};

    2 分隔链表

    【概述】穿针引线 重组
    【题目描述**】
    给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。
    【题目示例**】

    输入：head = 1->4->3->2->5->2, x = 3
输出：1->2->2->4->3->5

    【题目分析**】**
    本题要求对链表按照大于小于 x 进行分类。由于没有说不能用额外空间，所以我们可以将小于 x 的节点放至一个链表，大于 x 的节点放至另一个节点，之后再合并两个链表即可。

  5. 【分】使用指针 cur 遍历整个链表，将各节点摘至对应链表。

  6. 【和】小于 x 链表的尾部和 大于 x 链表的头部相连，大于 x 链表连接空。

【逻辑分析**】**

  1. 创建两个链表的头尾节点 p1_end p1_start p2_end p2_start 。
  2. 使用指针 cur 从 head 节点遍历链表，如果遇到大于 x 的节点，进入 p1 串，尾结点 p1_end 进一步；反之进入 p2 串，尾结点 p2_end 进一步。
  3. 将两个子串头尾连接，p1_end.next = p2_start.next p2_end.next = null。

  4. 返回 p1_start.next 即为所求。

    var partition = function(head, x) {
if(!head || !head.next) return head;
let p1_end = p1_start = new ListNode(-1);
let p2_end = p2_start = new ListNode(-1);
let cur = head;
while( cur ){
  if( cur.val < x ) p1_end = p1_end.next = cur;
  else p2_end = p2_end.next = cur;
  cur = cur.next;
}
p1_end.next = p2_start.next;
p2_end.next = null;
return p1_start.next;
};

    3 奇偶链表

    【概述】穿针引线 重组
    【题目描述**】
    给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
    请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。
    【题目示例**】

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

    【题目分析**】**
    本题要求对链表奇偶重排。简单来说就是将奇数连在一起，偶数连在一起，然后接一块。由于要求原地算法 ，所以应避免【分隔链表】中新建头尾结点，尽量不创建新节点。

  5. 【整体】= 【奇数链】【偶数链】，由于不创建新节点，需要用 even 和 odd 分别遍历两条链。这样的问题就是两链头结点需要单独用变量记录。

  6. 【奇数链】以 head 为头结点，每次接 odd.next 。

  7. 【偶数链】以 head.next 为头结点，每次接 even.next 。**

    var oddEvenList = function(head) {
if( !head || !head.next ) return head;
const dummy = new ListNode(-1,head);
let even = head , odd = head.next;
const tmp = odd;
while( odd && odd.next ){
  even = even.next = odd.next ;
  odd = odd.next = even.next ;
}
even.next = tmp;

return dummy.next;
};

    4 排序链表

    【概述】穿针引线 排序
    【题目描述**】
    给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
    PS： 在 O(n log n) 时间复杂度和常数级空间复杂度下对链表进行排序。
    【题目示例**】

    head = [4,2,1,3]
输出：[1,2,3,4]

    【题目分析**】**
    本题要求对链表进行复杂度为 O(nlogn) 的排序，即归并排序。首先要了解【归并排序】的过程，简单的说就是【归】和【并】：

  8. 【归】将链表划分为两个更小的子串。

  9. 【并】将两个链表按照升序合并。

【逻辑分析**】**

  1. 通过【快慢指针】将链表从中间位置划分成两个子串，代码见【链表的中间结点】。
  2. 将两个子串再次传入排序函数，继续递归。
  3. 将两个子串按照升序合并，见【合并两个有序链表】 。
    const merge = (l,r)=>{
const dummy = new ListNode(undefined);
let p = dummy;
while( l && r ){
  if( l.val > r.val ){
      p = p.next = r;
      r = r.next;
  }else{
      p = p.next = l;
      l = l.next;
  }
}
p.next = r ? r : l;
return dummy.next;
}
var sortList = function(head) {
if( !head || !head.next ) return head;
let slow = head , fast = head.next;
while( fast && fast.next ){
  slow = slow.next;
  fast = fast.next.next;
}
const mid = slow.next;
slow.next = null;
const left = sortList(head);
const right = sortList(mid);
return merge(left,right);
};

    5 重排链表

    【概述】穿针引线 合并
    【题目描述**】
    给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
    你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
    【题目示例**】
    给定链表 1->2->3->4, 重新排列为 1->4->2->3.
    【题目分析**】
    本题要求对链表前后交错重排。需要同时知道链表前后的信息，不能顺序读取，所以需要借助其他数据结构。最直接的方式就是将链表记录在    【栈】里，然后通过索引读取对应节点，依次连接。
    【逻辑分析**】
    var reorderList = function(head) {
const stack = [];
while(head){
  const tmp = head.next;
  head.next = null;
  stack.push(head);
  head = tmp;
}
let i = -1 , j = stack.length;
while(++i<--j){
  stack[i].next = stack[j];
  j !== i + 1 && (stack[j].next = stack[i + 1]);
}
head = stack[0];
};

二、快慢指针

类型概述

【链表】的问题之一是无法高效的获取长度、元素位置信息，所以有一类题便是围绕这一点展开的，诸如获取倒数第 **k** 个元素，获取中间位置的元素，判断是否有环等等与位置有关的问题。这类题目一般的解决方案就是【快慢指针】。

题型一 | 相对位置

题型串联

1 链表的中间结点

【概述】快慢指针
【题目描述**】
给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
【题目示例**】

[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])

【题目分析**】
本题要求找到链表的中点。思路比较简单，慢指针 slow 走一步，快指针 fast 走两步即可。
【逻辑分析**】

  1. 快慢指针都从 head 出发，由于 fast 要走两步，所以要确保 fast 和 fast.next 都存在。
  2. 每一次遍历，快慢指针同时前进。
  3. 返回慢指针 slow 即为所求。
    var middleNode = function(head) {
if(!head) return null;
let slow = fast = head;
while(fast&&fast.next){
  slow = slow.next;
  fast = fast.next.next;
}
return slow;
};

    2 删除链表的倒数第N个节点

    【概述】快慢指针
    【题目描述**】
    给定一个链表，删除链表的倒数第 _n_ 个节点，并且返回链表的头结点。
    【题目示例**】
    给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
    【直观思路】先统计链表的长度 len ，然后遍历到 len-n-1 即可。
    【题目分析**】
    题目要求删除倒数第 N 个节点。涉及    【遍历】和【删除】**两个步骤。
  • 【遍历】由于要删除元素，我们要定位倒数 N+1 的位置。由于倒数第 N+1 的位置，可以看做距离链表尾部 N-1 个节点，所以可以用【快慢指针】进行定位，即快慢指针之间相距 N+1 。
  • 【删除】由于采用【快慢指针】，慢指针 slow 即为倒数第 N+1 的位置，删除只需 slow.next = slow.next.next 。

【逻辑分析**】**

  1. 因为涉及【删除】操作，我们先设置【哑结点】dummy 。
  2. 慢指针 slow 从 dummy 出发，快指针 fast 从 head 出发。PS：快慢指针一开始距离差就为 1 。
  3. 快指针 fast 先移动 n 个节点，与慢指针 slow 拉开差距。
  4. 快慢指针一起移动，直至快指针 fast 到达终点，此时 慢指针 slow 即为倒数第 N+1 的位置。
  5. 删除慢指针 slow 后一个节点。
  6. 返回【哑结点】dummy 下一指针，即为所求。
    var removeNthFromEnd = function(head, n) {
const dummy = new ListNode(-1,head);
let slow = dummy , fast = head;
for( let i = 0 ; i < n ; i++ ) fast = fast.next;
while(fast) fast=fast.next,slow=slow.next;
slow.next = slow.next.next;
return dummy.next;
};

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

    【概述】快慢指针
    【题目描述**】
    给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
    【题目示例**】
    输入: 1->1->2
输出: 1->2
    【题目分析**】**题目要求删除重复的元素，我们需要用慢指针 slow 定位重复元素的开头，用 fast 遍历重复元素。
  • 【连续元素不同】slow.val !== fast.next.val，指针同时进一位。
  • 【连续元素相同】快指针 fast 不停后移，直至 fast.next.val !=== slow.val 为止。

  • 此时 fast.next 是新一个不同元素，让 slow.next = fast.next 。

    var deleteDuplicates = function(head) {
  const dummy = new ListNode(-1,head);
  let slow = fast = head;

  while(fast && fast.next){
      if(slow.val !== fast.next.val ) slow=slow.next,fast=fast.next;
      else{
          while( fast.next && slow.val===fast.next.val) fast = fast.next;
          slow.next = fast.next;
      }
  }
  return dummy.next;
};

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

    【概述】快慢指针
    【题目描述**】
    给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
    【题目示例**】

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

    【题目分析**】**跟【删除排序链表中的重复元素】区别在于我们的慢指针 slow 指向重复元素的前一个，所以此时 慢指针 slow 的初始值为 head 的前一个（用哑结点表示）。

    var deleteDuplicates = function(head) {
  const dummy = new ListNode(-1,head);
  let slow = dummy, fast = head;

  while(fast && fast.next){
      if(slow.next.val !== fast.next.val ) slow=slow.next,fast=fast.next;
      else{
          while( fast.next && slow.next.val===fast.next.val) fast = fast.next;
          slow.next = fast.next;
          fast = fast.next;
      }
  }
  return dummy.next;
};

    题型二 | 环形链表

    题型串联

    1 环形链表

    【概述】快慢指针
    【题目描述**】
    给定一个链表，判断链表中是否有环。
    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 。
    【题目示例**】

    输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

    【题目分析**】**一般成环问题采用【快慢指针】处理，当快慢指针交汇时，说明有环。所以我们让慢指针 slow 走一步，快指针 fast 走两步，如果两者最终交汇说明有环。

    var hasCycle = function(head) {
  if(!head) return false;
  let slow = fast = head;
  while(fast.next && fast.next.next ){
      slow = slow.next;
      fast = fast.next.next;
      if(slow===fast) return true;
  }
  return false;
};

    2 环形链表 II

    【概述】快慢指针
    【题目描述**】
    给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
    为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
    说明：不允许修改给定的链表。
    【题目示例**】

    输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

    【题目分析**】**本题为【环形链表】问题的进一步深入，我们继续以 快慢指针初始值为 head ，快指针 fast 步速是慢指针slow 的两倍为出发点。

    • 【第一次相遇】
      • 【无环】fast 走到链表末尾，返回 null 。
      • 【有环】fast === slow ，两指针相遇，此时两者的步数关系为：
        • 【前提】假设链表的结构为 [<-a->][<-b->]，其中 a 为到环入口的节点数，b 为环的节点数。
          1. fast 的步数是 slow 的二倍，f = 2s 。
          2. fast 比 slow 的多走 n 个环，f=s+nb。
          3. 两式子相减为：f=2nb，s=nb ，即 fast 和 slow 指针都走了 2n ，n 个环的周长。
      • 【分析下】
        • 我们的目标时找到环的入口即 a+nb 位置，其中 n 取 0……n，所以我们再让慢指针 slow 走 a 步即可。
        • 开始我们不知道 a 怎么办？这是我们再让个指针从 head 出发，和 慢指针 slow 再走 a 步，也就是 新指针位置是 a ，慢指针 slow 位置是 a+nb ，两者会重合。
    • 【第二次相遇】
      • 慢指针 slow 位置不变，快指针 fast 重新指向 head ，然后一起相前冲。
      • 当 slow===fast 的时候，说明到环的入口。
        var detectCycle = function(head) {
let slow = fast = head;
while(1){
if(!fast || !fast.next) return null;
slow = slow.next , fast = fast.next.next;
if( fast === slow ) break;
}
fast = head;
while( fast !== slow ) fast = fast.next , slow = slow.next;
return fast;
};