leetcode刷题（javaScript）——链表相关场景题总结

��链表中的元素在内存中不是顺序存储的，而是通过next指针联系在一起的。常见的链表有单向链表、双向链表、环形链表等

在 JavaScript 刷题中涉及链表的算法有很多，常见的包括：

1. 遍历链表：从头到尾遍历链表，处理每个节点的值或指针。

2. 反转链表：将链表的指针方向反转，使链表的尾部变为头部。

3. 合并两个有序链表：将两个有序链表合并成一个有序链表。

4. 删除链表中的指定节点：删除链表中特定值或位置的节点。

5. 检测链表中是否有环：判断链表中是否存在环形结构。

对于新手刷题链表，一些需要注意的方法和建议包括：

1. 熟悉链表的基本操作：了解链表的基本结构和操作，包括节点的定义、指针操作等。

2. 注意边界情况：在处理链表时，要考虑边界情况，如空链表、只有一个节点的链表等。

3. 使用递归：递归是解决链表问题的常见方法，可以简化问题的复杂度。

4. 双指针技巧：在解决链表问题时，双指针技巧经常会派上用场，例如快慢指针用于检测环。

5. 利用辅助数据结构：有时候可以借助辅助数据结构如哈希表来解决链表问题。

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路：新创建一个链表，链表头指针pre，新的链表用pre指向，最后返回这个头指针。

1——》2——》3——》4——》5——》null

可以转换为

null《——1《——2《——3《——4《——5

pre初始是空对象pre = null

难点来了

怎么实现null《——1 让1的next指向null呢？

如果1的next改变指向，那么2以及之后的数据将丢失，所以需要提前将1的next暂存给一个变量；

然后这个时候可以改变1的next指向为pre了。

那原始链表还需要遍历呀，这个时候将暂存的next赋给current。同时pre也从null后移指向1.所以第二次遍历结束

2——》3——》4——》5——》null

^

current指向2

null《——1

                ^

                pre指向

第三次遍历结束

3——》4——》5——》null

^

current指向3

null《——1《——2

                             ^

                        pre指向

这道题可能当时做会了过段时间就忘了，所以要牢记改变指向的时候数据连接会丢失，需要考虑丢掉还是要保留，如果要保留数据，一定在改变指向前处理。

/** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var reverseList = function (head) {    let prev = null;    let current = head;    while (current !== null) {        let nextNode = current.next;        current.next = prev;        prev = current;        current = nextNode;    }    return prev;};

 使用迭代的方式遍历链表，将每个节点的指针方向反转。使用 prev 指针来保存已经反转部分的链表，current 指针来遍历原始链表。在每一步中，我们将 current.next 指向 prev，然后更新 prev 和 current 指针继续向后移动，直到遍历完整个链表。

最后，返回反转后的链表的头节点，即 prev 指针所指向的节点，这个节点就是原始链表的尾节点，也就是反转后链表的头节点。

21. 合并两个有序链表

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

/** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} list1 * @param {ListNode} list2 * @return {ListNode} */var mergeTwoLists = function (list1, list2) {    if (!list1) return list2;    if (!list2) return list1;        let head = new ListNode(0, null);    let cur = head;    while (list1 && list2) {        let val;        if (list1.val    
 为了正确地创建 ListNode 的实例，应该使用 new ListNode(val, null)而不是ListNode(val,null)这是因为创建的是节点的实例而不是单纯的调用函数。这里的ListNode是构造函数。
    
怎么区分普通函数和构造函数？
  

• 看大小写：一般构造函数函数名的首字母会大写，普通函数是小写。
• 函数中的this指向不同：普通函数的this在严格模式下指向undefined，非严格模式指向window对象。构造函数的this指向它创建的对象实例。

  构造函数的执行流程

  •     立即创建一个新的对象
  •     将新建的对象设置给函数中的this,在构造函数中可使用this来引用新建的对象
  •     逐行执行函数中的代码
  •     将新建的对象作为返回值返回

    237. 删除链表中的节点——改变元素指向

    有一个单链表的 head，我们想删除它其中的一个节点 node。

    给你一个需要删除的节点 node 。你将 无法访问 第一个节点  head。

    链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

    删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

    • 给定节点的值不应该存在于链表中。
    • 链表中的节点数应该减少 1。
    • node 前面的所有值顺序相同。
    • node 后面的所有值顺序相同。

      思路：不删除当前node节点，又没有上一个元素的信息，不能更改上一个元素指向node.next。从node出发，让node变成node.next，跳过node.next这个节点。我变成了他，同时，让他消失。。

      /** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} node * @return {void} Do not return anything, modify node in-place instead. */var deleteNode = function(node) {    node.val = node.next.val;    node.next = node.next.next;};

       node.val = node.next.val让node替换成node.next元素

      node.next = node.next.next 干掉node.next

      node替代node.next结束

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

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

      /** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var deleteDuplicates = function (head) {    if (!head) return head;    let cur = head;    while (cur.next) {        if (cur.val === cur.next.val) {            cur.next = cur.next.next;        } else {            cur = cur.next;        }    }    return head;};

       思路：比较简单的链表删除，题目已经保证是排序好的链表，只用考虑相邻元素重复的情况。当前元素和下一个元素重复的话，将当前元素的next指向，下下一个元素。跳过重复的。

      如果没有重复，指针往后移动一个。注意需要返回排序后的数组，所以头指针的指向不能变，最后返回head指针。过程用cur指针替代head进行向后移动。

       141. 环形链表——快慢指针

      如果链表中存在环，快指针和慢指针最终会在环中相遇；如果链表中不存在环，快指针会先到达链表尾部。

      给你一个链表的头节点 head ，判断链表中是否有环。

      如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

      如果链表中存在环 ，则返回 true 。 否则，返回 false 。

      使用快慢指针的技巧来检测链表中是否存在环。具体来说，定义了两个指针 f 和 s，初始时都指向链表的头部。然后，使用一个循环来遍历链表，其中快指针 f 每次移动两步，慢指针 s 每次移动一步。如果链表中存在环，快指针 f 会在某个时刻追上慢指针 s，此时就可以判断链表中存在环，返回 true；如果快指针 f 到达链表尾部（即 f 或 f.next 为 null），则说明链表中不存在环，返回 false。

      这种算法的时间复杂度为 O(n)，其中 n 是链表的长度。

      /** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var hasCycle = function (head) {    let f = head, s = head;    while (f != null && f.next != null) {        s = s.next;        f = f.next.next;        if (s == f) return true;    }    return false;};

       使用双等号 == 运算符来比较两个对象并不会直接比较它们的内容，而是比较它们的引用。

      s==f则快指针和慢指针指向了同一个对象

       160. 相交链表

      给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

      图示两个链表在节点 c1 开始相交：

      题目数据 保证 整个链式结构中不存在环。

      注意，函数返回结果后，链表必须 保持其原始结构 。

      这道题，如果不看题解，第一次做肯定没有思路

      首先比较的不是节点的值相等，而是指向同一个节点。

      其次，一般会考虑n^2时间复杂度，穷举A，对A的每项在穷举B

      其实只要找到A、B的起始位，让A和B可以同步向后 移动。

      例如，上图中，如果B一开始指向b2，那么比较b2和a1，不相等，均向后移动一位，比较a2和b3是否相等。不等，在往后移动，比较c1和c1是否相等，相等则返回A或B当前指向的节点

       要找出两个单链表相交的起始节点，可以使用双指针法。具体步骤如下：

      1. 分别遍历两个链表，计算它们的长度。
      2. 计算两个链表的长度差，然后让较长的链表的指针先移动长度差个节点，使得两个链表剩余的长度相等。
      3. 同时遍历两个链表，比较节点是否相同，找到相交的起始节点。

      /** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */var getIntersectionNode = function (headA, headB) {    let curA = headA;    let curB = headB;    let lengthA = getLength(curA);    let lengthB = getLength(curB);    if (lengthB > lengthA) {        let step = lengthB - lengthA;        while (step--) {            curB = curB.next;        }    } else if (lengthB    
       注意在计算链表长度时不要破坏传入的head指针指向，要创建新的变量指向head指针。
        
      拿到lengthA和lengthB后可以判断哪个更长，移动长的链表的cur指针。
        
      A和B的cur指针同步移动时无论判断while(curA)还是while(curB)都可以，因为剩余要比较的链表长度相等呀，比较次数也相等
        
      当A和B的cur指向一样，同理，返回curA或curB都行，结束判断
        
       203. 移除链表元素
       
      给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
       
      示例 1：
       
      输入：head = [1,2,6,3,4,5,6], val = 6输出：[1,2,3,4,5]
       
      示例 2：
       
      输入：head = [], val = 1输出：[]
       
      示例 3：
       
      输入：head = [7,7,7,7], val = 7输出：[]                  
         
      思路：这道题诈看很简单，用指针遍历，当前元素和val相等时，用下一个元素替换当前元素。这种方法在最后一个元素时会失效，因为无法杀***最后一个元素了，最后一个元素和它前一个连接无法断开。
        
      那如果在头节点之前新增一个节点呢，用cur的next节点参与比较。当遇到最后一个元素时，其实是示例中的5.next ===6，让5.next=null即可，杀***了最后一个元素6
        
      /** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @param {number} val * @return {ListNode} */var removeElements = function (head, val) {    let newNode = new ListNode(0, head);    let cur = newNode;    while (cur) {        if (cur.next && cur.next.val === val) {            cur.next = cur.next.next;        } else {            cur = cur.next;        }    }    return newNode.next;};
         
       这里用newNode指向新创建的链表，最后返回的是newNode.next，因为头加入了一个无用的节点。
        
      用next节点参与比较，当前元素改变它的next指向即可
        
       876. 链表的中间结点
       
      给你单链表的头结点 head ，请你找出并返回链表的中间结点。
       
      如果有两个中间结点，则返回第二个中间结点。
          
      方法一：首先遍历一遍单链表，记录链表的长度len，计算中间节点的位置。 用空间换时间：
        
      /** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var middleNode = function (head) {    let cur = head;    let setp = Math.floor(getLength(head) / 2);    while (setp--) {        cur = cur.next;    }    return cur;};function getLength(head) {    let cur = head;    let length = 0;    while (cur) {        length++;        cur = cur.next;    }    return length;}
         
       当我用这种方法写完，时间复杂度n+n/2感觉没那么简单，一看评论区，果然大神就是多，双指针，时间复杂度为n，一趟排序就找到中间位置了。
          
      方法二：利用快慢指针，快指针每次走两步，慢指针每次走一步，所以快指针走的距离为慢指针的两倍，故当快指针遍历到链表末尾时，慢指针指向记为中间节点 
        
      /** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {ListNode} */var middleNode = function (head) {    let f = head;    let s = head;    while (f && f.next) {        f = f.next.next;        s = s.next;    }    return s;};
         
       简直了，只要思想简单，代码就简单。这里判断f.next.next最后一步是等于null所以f.next不能为null，f也不能为null。
        
       1290. 二进制链表转整数
       
      给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
       
      请你返回该链表所表示数字的 十进制值 。
          
       思路：我原称这是一道数学题
        
      让2进制转10进制，头节点是2进制的高位，尾节点是2进制的低位，一般可以将链表翻转，从低位开始用x*2的length次方逐步求和。但是也可以从高位到低位逐步求和。怎么从高位到低位呢
        
      示例：1011 =11
        
      第一个元素 1=result
        
      到第二个元素，知道长度为2 将上一个结果*2+当前元素0=2=result
        
      到第三个元素，知道长度为3，前两个都少个2，由于2是公共乘数，可以将2提出来，2*result+1=5=result
        
      到第四个元素，知道长度为4，同理2*result+1=11=result
        
      结束，每个缺失的2都补上了
        
      /** * Definition for singly-linked list. * function ListNode(val, next) { *     this.val = (val===undefined ? 0 : val) *     this.next = (next===undefined ? null : next) * } *//** * @param {ListNode} head * @return {number} */var getDecimalValue = function (head) {    let result = 0;    let cur = head;    while (cur) {        result =( result