# 基本概念
链表是一种常见的基础数据结构,是一种线性表。链表通常由一连串节点组成,每个节点包含任意的实例数据和一或两个用来指向上一个/或下一个节点的指针。 节点结构如下
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val)
this.next = (next === undefined ? null : next)
}
生活中常见的例子也非常多,例如火车,寻宝游戏等等。
# 特点
向链表中插入元素的时间复杂度为 ,查找/删除的时间复杂度则为 。
# 常见操作(必须掌握)
我们对于链表的操作其实都是对于指针的操作,模版基本都是固定的,多多练习即可掌握。
- 链表遍历
// head 是头节点 let current = head while (current) { // doSomething current = current.next }
- 插入
找到待插入位置的前驱节点 temp = 待插入位置的前驱节点.next 待插入位置的前驱节点.next = 待插入节点 待插入节点.next = temp
- 删除
找到待删除位置的前驱节点 待删除位置的前驱节点.next = 待删除位置的前驱节点.next.next
- 206. 链表反转 (opens new window)
使节点的next指向它的前驱节点。var reverseList = function(head) { let prev = null let current = head while (current) { const next = current.next current.next = prev prev = current current = next } return prev }
- 141. 环形链表 (opens new window)
利用快慢指针判断链表中是否有环,快指针一次走两步,慢指针一次走一步,如快慢指针相遇则说明存在环形。或者利用哈希表来进行判断。var hasCycle = function(head) { if(head == null || head.next == null) { return false } let slow = head let fast = head.next while(slow != fast) { if(fast == null || fast.next == null) { return false } slow = slow.next fast = fast.next.next } return true }
- 160. 相交链表 (opens new window)
利用哈希表或者双指针来解决。var getIntersectionNode = function(headA, headB) { const map = new Map() while(headA) { map.set(headA, headA) headA = headA.next } while(headB) { if(map.has(headB)) { return headB } headB = headB.next } return null }
# 常见技巧
- 画图
遇到链表问题,我们首先需要画图,找出解法,然后用代码实现。 - 使用虚拟头/尾节点
它们是纯功能的,通常不保存任何数据,其主要目的是使链表标准化,如使链表永不为空、永不无头、简化插入和删除。 - 使用快慢指针
主要用来解决链表是否存在环,中间节点,相交等问题。 代码模版let slow = head let fast = head while(fast && fast.next) { slow = slow.next fast = fast.next.next if(slow == fast) { return true } }
- 边界条件
在调用 next 字段之前,始终检查节点是否为空。
# 推荐题目(应该掌握的题目)
- 简单
- 中等
# 更多文章
- javascript数据结构与算法第三版
- leetcode-链表 (opens new window)
- 力扣加加-链表专题 (opens new window)