每日一博 | 单链表解题思维

一、概念

链表由一组零散的结点通过指针连接而成，每个结点都包含当前结点内容和后继指针。相对于数组，它不受固于存储空间的限制，可更快捷地进行插入和删除操作，主要有以下几种类型：

1、单链表

指针指向下一个节点，终点指向null

2、双链表

指针指向前一个节点和后一个节点

3、循环链表

最后一个节点指向第一个节点

在解决链表相关问题时，先执行三步骤，再敲下代码会更清晰

• 确定解题的链表类型
• 画图理清思路
• 确定边界条件

不同于数组，JS官方还没有提供一个直接的链表API，可通过对象的方式模拟出链表，其结构为

const head = { data: 1, next: { data: 2, next: null, }, }; 

二、leetcode 最常见相关题型

1、合并两个有序链表

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

示例: 输入: l1 = [1,2,4], l2 = [1,3,4] 输出: [1,1,2,3,4,4] 

步骤：

• 解题的链表类型是单链表
• 思路：
  • l1 与 l2 是有序递增的，因此 l1.val 与 l2.val 的较小值就是合并后链表的最小值
  • 依次递归 大小节点的比较，直到 l1 l2 均为 null
• 边界条件：递归到任意链表为 null 即可停止，并将 next 指向另外的链表

var mergeTwoLists = function(l1, l2) { if (l1 === null) { return l2 } else if (l2 === null) { return l1 } else if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2) return l1 } else { l2.next = mergeTwoLists(l2.next, l1) return l2 } }; 

2、环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。如果链表中存在环，返回 true 否则返回 false 。要求用 O(1) 内存解决此问题

pos 表示链表尾连接到链表中的位置，若 pos 是 -1 则该链表中没有环

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

步骤：

• 解题的链表类型是单链表
• 思路：
  • 龟兔赛跑算法：利用快慢双指针，快指针走两步，慢指针走一步
  • 如果链表存在环，则两个速度不同的指针必定会相遇。并且从相遇点和链表头结点同时往下走，会在环起点相遇
• 边界条件：
  • 快指针指向 null 停止，无环
  • 快慢指针指向同一个节点，有环

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

3、反转链表

给你单链表的头节点 head ，请你使用迭代或递归地反转链表，并返回反转后的链表

示例: 输入: head = [1,2,3,4,5] 输出: [5,4,3,2,1] 

步骤：

• 解题的链表类型是单链表
• 迭代思路：
  • 将单链表的每个节点的后继指针指向它的前驱节点

• 边界条件：
  • 当链表 null 停止
  • 链表仅有一个节点

var reverseList = function(head) { if(!head || !head.next) return head; let prev = null; let cur = head; while(cur) { const curNext = cur.next; // 反转后赋值给prev指针 cur.next = prev; prev = cur; // 链接到下一个节点 cur = curNext; } return prev }; 

4、链表的中间结点

给定一个头结点为 head 的非空单链表，返回链表的中间结点，如果有两个中间结点，则返回第二个中间结点（给定链表的结点数介于 1 和 100 之间）

示例: 输入: [1,2,3,4,5] 输出: 3 输入: [1,2,3,4,5,6] 输出: 4 

步骤：

• 解题的链表类型是单链表
• 思路：
  • 快指针p2的位移是慢指针p1的2倍，所以当p2走到链表尾部时，p1刚好走了一半，指向链表的中点。
  • 下题同理

• 边界条件：
  • 快指针指向 null 时，慢指针刚好处于中间位置

var middleNode = function(head) { if(!head || !head.next) return head; let slow = head; let fast = head; while(fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow }; 

5、删除链表倒数第 n 个结点

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

示例： 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5] 

步骤：

• 解题的链表类型是单链表

• 思路：

  • 快指针一次性走完n个节点，接着两个指针一起往后走，直到快指针指向null，此时慢指针就是倒数第n个节点
  • 添加哨兵处理第n个节点

• 边界条件：

  • 快指针指向 null 时，慢指针所在位置就是倒数第n个节点

const removeNthFromEnd = function (head, n) { // 哨兵 let preHead = new ListNode(0) preHead.next = head let slow = preHead; let fast = preHead; // 先走n步 while (n--) { fast = fast.next } // 一起走 while (fast && fast.next) { fast = fast.next slow = slow.next } slow.next = slow.next.next return preHead.next; }; 

6、回文链表

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

示例: 输入: head = [1,2,2,1] 输出: true 

步骤：

• 解题的链表类型是单链表

• 思路：

  • 借助数组，将链表丢进数组
  • 设置前后指针，前后指针理应相同，若不同则不是回文
  • 循环结束若没有返回false则是回文

• 边界条件：

  • 前后指针不一致
  • 循环结束

var isPalindrome = function (head) { const res = [] while (head) { res.push(head.val); head = head.next } let pre = 0; let last = res.length - 1; while (pre < last) { if (res[pre] !== res[last]) return false; pre++; last--; } return true } 

8、相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。题目数据保证整个链式结构中不存在环。

注意：

• 函数返回结果后，链表必须 保持其原始结构(需复制新的链表)
• 如果两个链表没有交点，返回 null
• 程序尽量满⾜ O(n) 时间复杂度，且仅⽤ O(1) 内存

示例: 输入：intersectVal = 4, listA = [1,2,3,4,5], listB = [6,7,4,5], skipA = 3, skipB = 2 // 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 2 个节点 输出：Intersected at '4' // 相交节点的值为 4 （注意，如果两个链表相交则不能为 0） 

步骤：

• 解题的链表类型是单链表
• 思路：
  • 同上，寻找AB链表的高度差并消除，已知相交点之后的长度必须相等
  • AB双指针同时前进，当短链表B的指针遍历完成时，双指针的长度差刚好是双链表的长度差，将B指针指向A链表的头节点，跟着A指针再一次遍历，直到A指针遍历完成
  • 同样将A指针指向B链表的头节点，B指针向前一步，则消除了链表的高度差

• 边界条件：
  • 指针指向null时，切换指向链表
  • AB链表值相等

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

9、链表求和

给定两个用链表表示的整数，每个节点包含一个数位，这些数位是反向存放的，也就是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果

示例： 输⼊：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295 输出：2 -> 1 -> 9，即912 

步骤：

• 解题的链表类型是单链表

• 思路：

  • 输出的是新链表，因此需要创建一个链表
  • 由于是反向存储，则链表从个位数开始计算，大于十则进位
  • 进位，首先考虑⽤carry存储每次的进位，余数存储进创建的节点

• 边界条件：

  • 双链表指向null时，遍历完成
  • 遍历完成，carry不为0，则还需前进一位

const addTwoNumbers = function (l1, l2) { // 哨兵 let preHead = new ListNode(0) let carry = 0; let pre = preHead; while (l1 || l2) { let sum = 0; if (l1) { sum += l1.val l1 = l1.next } if (l2) { sum += l2.val l2 = l2.next } sum += carry carry = Math.floor(sum / 10) pre.next = new ListNode(sum % 10) pre = pre.next } if (carry > 0) { pre.next = new ListNode(carry) pre = pre.next } return preHead.next } 

进阶：思考⼀下，假设这些数位是正向存放的，⼜该如何解决呢? 输⼊：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295 输出：9 -> 1 -> 2，即912