节点定义:
class ListNode {
val
next
constructor(value, next) {
this.val = value
this.next = next
}
}
链表操作分为加虚拟头节点和虚拟不加头节点两种:
- 不加虚拟头节点:针对首元节点要特殊处理
- 加虚拟头节点:算法一致(推荐)
虚拟头节点设置:let dummyNode = new ListNode(undefined, head)
删除节点
核心算法:p.next = p.next.next
leetcode:
- 203. 移除链表元素 - 力扣(LeetCode)
- 19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode) (结合快慢指针)
- 83. 删除排序链表中的重复元素 - 力扣(LeetCode) (不需要虚拟头节点)
- 82. 删除排序链表中的重复元素 II - 力扣(LeetCode) (需要虚拟头节点)
反转链表
先添加一个空节点,然后记住当前节点的下一个节点,最后反向链接
leetcode:
环形链表
判断有环:快慢指针
快的每次走 2 步,慢的每次走 1 步,如果相遇则是有环