# 基本概念

链表是一种常见的基础数据结构,是一种线性表。链表通常由一连串节点组成,每个节点包含任意的实例数据和一或两个用来指向上一个/或下一个节点的指针。 节点结构如下

function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val)
    this.next = (next === undefined ? null : next)
}

生活中常见的例子也非常多,例如火车,寻宝游戏等等。

# 特点

向链表中插入元素的时间复杂度为 O(1)O(1) ,查找/删除的时间复杂度则为 O(n)O(n)

# 常见操作(必须掌握)

我们对于链表的操作其实都是对于指针的操作,模版基本都是固定的,多多练习即可掌握。

  • 链表遍历
    // 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 字段之前,始终检查节点是否为空。

# 推荐题目(应该掌握的题目)

# 更多文章