解题套路

链表分类

按照是否循环分为：循环链表和非循环链表

按照指针个数分为：单链表和双链表

反转链表

1. 将某个链表进行反转
2. 在 O(n) 时间, O(1) 空间复杂度下逆序读取链表的某个值
3. 将某个链表按 K 个一组进行反转

这种题，直接套用模版，伪代码如下:

当前指针 =  头指针
前一个节点 = null;
while 当前指针不为空 {
	下一个节点 = 当前指针.next;
    当前指针.next = 前一个节点
    前一个节点 = 当前指针
    当前指针 = 下一个节点
}
return 前一个节点;

JS 代码参考:

let cur = head;
let pre = null;
while (cur) {
  const next = cur.next;
  cur.next = pre;
  pre = cur;
  cur = next;
}
return pre;

复杂度分析

• 时间复杂度：O(N)

• 空间复杂度：O(1)

合并链表

1. 将两条有序或无序的链表合并成一条有序链表
2. 将 k 条有序链表合并成一条有序链表

伪代码:

ans = new Node(-1) // ans 为需要返回的头节点
cur = ans
// l1和l2分别为需要合并的两个链表的头节点
while l1 和 l2 都不为空
    cur.next = min(l1.val, l2.val)
    更新较小的指针，往后移动一位
if l1 == null
   cur.next = l2
if l2 == null
   cur.next = l1
return ans.next

JS 代码参考:

let ans = (now = new ListNode(0));
while (l1 !== null && l2 !== null) {
  if (l1.val < l2.val) {
    now.next = l1;
    l1 = l1.next;
  } else {
    now.next = l2;
    l2 = l2.next;
  }
  now = now.next;
}

if (l1 === null) {
  now.next = l2;
} else {
  now.next = l1;
}
return ans.next;

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

相交或环形链表

1. 判断某条链表是否存在环
2. 获取某条链表环的大小
3. 获取某两条链表的相交节点

链表相交求交点

解法一：哈希法

• 有 A, B 这两条链表, 先遍历其中一个，比如 A 链表, 并将 A 中的所有节点存入哈希表。
• 遍历 B 链表,检查节点是否在哈希表中, 第一个存在的就是相交节点

伪代码：

data = new Set() // 存放A链表的所有节点的地址

while A不为空{
  哈希表中添加A链表当前节点
  A指针向后移动
}

while B不为空{
  if 如果哈希表中含有B链表当前节点
    return B
  B指针向后移动
}

return null // 两条链表没有相交点

JS 代码参考

let data = new Set();
while (A !== null) {
  data.add(A);
  A = A.next;
}
while (B !== null) {
  if (data.has(B)) return B;
  B = B.next;
}
return null;

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

解法二：双指针

• 例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
• 当 a 到达链表的尾部时,重定位到链表 B 的头结点
• 当 b 到达链表的尾部时,重定位到链表 A 的头结点。
• a, b 指针相遇的点为相交的起始节点，否则没有相交点

伪代码:

a = headA
b = headB
while a,b指针不相等时 {
    if a指针为空时
      a指针重定位到链表 B的头结点
    else
      a指针向后移动一位
    if b指针为空时
      b指针重定位到链表 A的头结点
    else
      b指针向后移动一位
}
return a

JS 代码参考:

var getIntersectionNode = function (headA, headB) {
  let a = headA,
    b = headB;
  while (a != b) {
    a = a === null ? headB : a.next;
    b = b === null ? headA : b.next;
  }
  return a;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(1)

环形链表求环的起点

解法一：哈希法

• 遍历整个链表,同时将每个节点都插入哈希表,
• 如果当前节点在哈希表中不存在,继续遍历,
• 如果存在,那么当前节点就是环的入口节点

伪代码：

data = new Set() // 声明哈希表
while head不为空{
  if 当前节点在哈希表中存在{
    return head // 当前节点就是环的入口节点
  } else {
    将当前节点插入哈希表
  }
  head指针后移
}
return null // 环不存在

JS 代码参考:

let data = new Set();
while (head) {
  if (data.has(head)) {
    return head;
  } else {
    data.add(head);
  }
  head = head.next;
}
return null;

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

解法二：双指针

• 定义一个 fast 指针,每次前进两步,一个 slow 指针,每次前进一步

• 当两个指针相遇时 i. 将 fast 指针指向链表头部,同时 fast 指针每次只前进一步 ii. slow 指针继续前进,每次前进一步

• 当两个指针再次相遇时,当前节点就是环的入口

伪代码:

fast = head
slow = head //快慢指针都指向头部
do {
  快指针向后两步
  慢指针向后一步
} while 快慢指针不相等时
if 指针都为空时{
  return null // 没有环
}
while 快慢指针不相等时{
  快指针向后一步
  慢指针向后一步
}
return fast

JS 代码参考：

if (head == null || head.next == null) return null;
let fast = (slow = head);
do {
  if (fast != null && fast.next != null) {
    fast = fast.next.next;
  } else {
    fast = null;
  }
  slow = slow.next;
} while (fast != slow);
if (fast == null) return null;
fast = head;
while (fast != slow) {
  fast = fast.next;
  slow = slow.next;
}
return fast;

题目推荐

• 21 合并两个有序链表
• 82 删除排序链表中的重复元素 II
• 83 删除排序链表中的重复元素
• 86 分隔链表
• 92 反转链表 II
• 138 复制带随机指针的链表
• 141 环形链表
• 142 环形链表 II
• 143 重排链表
• 148 排序链表
• 206 反转链表
• 234 回文链表