「🦆TSK的博客」

Appearance

On this page

链表 ​

定义 ​

ts
class ListNode {
  public val: number;
  public next: ListNode|null = null;
  constructor(value?: number,next?:ListNode|null) {
    this.val = value;
    this.next = next;
  }
}

链表的合并 ​

真题描述：将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的

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

做链表处理类问题，大家要把握住一个中心思想——处理链表的本质，是处理链表结点之间的指针关系。

js
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const mergeTwoLists = function(l1, l2) {
  // 定义头结点，确保链表可以被访问到
  let head = new ListNode()
  // cur 这里就是咱们那根“针”
  let cur = head
  // “针”开始在 l1 和 l2 间穿梭了
  while(l1 && l2) {
      // 如果 l1 的结点值较小
      if(l1.val<=l2.val) {
          // 先串起 l1 的结点
          cur.next = l1
          // l1 指针向前一步
          l1 = l1.next
      } else {
          // l2 较小时，串起 l2 结点
          cur.next = l2
          // l2 向前一步
          l2 = l2.next
      }
      
      // “针”在串起一个结点后，也会往前一步
      cur = cur.next 

  }
  
  // 处理链表不等长的情况
  cur.next = l1!==null?l1:l2
  // 返回起始结点
  return head.next
};

移除重复链表 ​

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

要深刻理解指针的概念,head 和 cur 的区别 2023/12/22 10:37

示例 1: 输入: 1->1->2 输出: 1->2 示例 2: 输入: 1->1->2->3->3 输出: 1->2->3

js
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function(head) {
// 设定 cur 指针，初始位置为链表第一个结点
let cur = head;
// 遍历链表
while(cur != null && cur.next != null) {
    // 若当前结点和它后面一个结点值相等（重复）
    if(cur.val === cur.next.val) {
        // 删除靠后的那个结点（去重）
        cur.next = cur.next.next;
    } else {
        // 若不重复，继续遍历
        cur = cur.next;
    }
}
return head;
};

移除重复链表2 ​

真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。

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

题干要求我们只要一个元素发生了重复，就要把它彻底从链表中干掉，一个不留。

其实在链表题中，经常会遇到这样的问题：链表的第一个结点，因为没有前驱结点，导致我们面对它无从下手。这时我们就可以用一个 dummy 结点来解决这个问题。

所谓 dummy 结点，就是咱们人为制造出来的第一个结点的前驱结点，这样链表中所有的结点都能确保有一个前驱结点，也就都能够用同样的逻辑来处理了。

我们首先要做的就是定义一个 dummy 结点，指向链表的起始位置：

这样一来，如果想要删除两个连续重复的值为 1 的结点，我们只需要把 dummy 结点的 next 指针直接指向 2：

js
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function(head) {
    // 极端情况：0个或1个结点，则不会重复，直接返回
    if(!head || !head.next) {
        return head
    }
    // dummy 登场
    let dummy = new ListNode() 
    // dummy 永远指向头结点
    dummy.next = head   
    // cur 从 dummy 开始遍历
    let cur = dummy 
    // 当 cur 的后面有至少两个结点时
    while(cur.next && cur.next.next) {
        // 对 cur 后面的两个结点进行比较
        if(cur.next.val === cur.next.next.val) {
            // 若值重复，则记下这个值
            let val = cur.next.val
            // 反复地排查后面的元素是否存在多次重复该值的情况
            while(cur.next && cur.next.val===val) {
                // 若有，则删除
                cur.next = cur.next.next 
            }
        } else {
            // 若不重复，则正常遍历
            cur = cur.next
        }
    }
    // 返回链表的起始结点
    return dummy.next;
};

dummy 结点

它可以帮我们处理掉头结点为空的边界问题，帮助我们简化解题过程。因此涉及链表操作、尤其是涉及结点删除的题目（对前驱结点的存在性要求比较高），我都建议大家写代码的时候直接把 dummy 给用起来，建立好的编程习惯：

移除链表元素 ​

题意：删除链表中等于给定值 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 输出：[]

使用虚拟头结点,因为头部也可能是要删除的节点

TIP

let cur = ret,是把 cur 当做了 ret 指针,其实还是一直在修改 ret, 只是 ret 没有移动

只有当 cur.next.val != val 才可以继续移动 cur

js
/**
  * @param {ListNode} head
  * @param {number} val
  * @return {ListNode}
  */
  var removeElements = function(head, val) {
      const ret = new ListNode(0, head);
      // 指针
      let cur = ret;
      while(cur.next) {
          if(cur.next.val === val) {
              cur.next = cur.next.next;
              continue;
          }
          cur = cur.next;
      }
      return ret.next;
  };

🔗反转链表 ​

题意：反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

接下来我们需要琢磨的是如何去反转指针的指向，这里我们需要用到三个指针，它们分别指向目标结点（cur）、目标结点的前驱结点（pre）、目标结点的后继结点（next）。这里咱们随便找个结点来开刀:

js
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const reverseList = function(head) {
    // 初始化前驱结点为 null
    let pre = null;
    // 初始化目标结点为头结点
    let cur = head;
    // 只要目标结点不为 null，遍历就得继续
    while (cur !== null) {
        // 记录一下 next 结点
        let next = cur.next;
        // 反转指针
        cur.next = pre;
        // pre 往前走一步
        pre = cur;
        // cur往前走一步
        cur = next;
    }
    // 反转结束后，pre 就会变成新链表的头结点
    return pre
};

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

题意：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

假设链表的长度是length，要删除倒数第n个节点，也就是删除正数第length-n+1个节点。

思路 ​

双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了（用空间换时间，本质上其实就是对关键信息进行提前记忆，这里咱们相当于用两个指针对差值实现了记忆）

js
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
 let t = new ListNode(0,head);
 let slow = t
 let fast =  t

// 先闷头走几步
 while(n--){
  fast = fast.next;
 }

// 然后并排走
 while(fast.next!=null){
  fast = fast.next;
  slow = slow.next
 }

 slow.next = slow.next.next;
 return t.next
};

链表相交 ​

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

例1:

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

例2:

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

思路 ​

使用 hash 记录

js
var getIntersectionNode = function(headA, headB) {
    const visited = new Set();
    let temp = headA;
    while (temp !== null) {
        visited.add(temp);
        temp = temp.next;
    }
    temp = headB;
    while (temp !== null) {
        if (visited.has(temp)) {
            return temp;
        }
        temp = temp.next;
    }
    return null;
};

使用 双指针

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

如何判断链表是否成环 ​

真题描述：给定一个链表，判断链表中是否有环。

示例 1： 输入：[3,2,0,4]（链表结构如下图） 输出：true 解释：链表中存在一个环

从 flag 出发，只要我能够再回到 flag 处，那么就意味着，我正在遍历一个环形链表。

js
/**
 * @param {ListNode} head
 * @return {boolean}
 */
// 入参是头结点 
const hasCycle = function(head) {
    // 只要结点存在，那么就继续遍历
    while(head){
        // 如果 flag 已经立过了，那么说明环存在
        if(head.flag){
            return true;
        }else{
            // 如果 flag 没立过，就立一个 flag 再往 下走
            head.flag = true;
            head = head.next;
        }
    }
    return false;
};

衍生题:

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

如果一个结点是环形链表成环的起点，那么它一定是第一个被发现 flag 标志已存在的结点：

这一点不难理解，我们试想如果从头开始遍历一个链表，假如途中进入了一个环，那么首先被打上 flag 标签的其实就是环的起点。待我们遍历完这个环时，即便环上所有的结点都已经被立了 flag，但起点处的 flag 一定最先被我们定位到。因此，我们只需要在第一次发现 flag 已存在时，将对应的结点返回即可：

js
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const detectCycle = function(head) {
    while(head){
        if(head.flag){
            // 说明是环的起点
            return head; 
        }else{
            head.flag = true;
            head = head.next;
        }
    }
    return null;
};

Updated at: