链表 (Linked List)

LeetCodeLinked List链表数据结构

链表 (Linked List)

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。

基础概念

链表类型

  1. 单链表
1 -> 2 -> 3 -> 4 -> NULL
  1. 双链表
NULL <- 1 <-> 2 <-> 3 <-> 4 -> NULL
  1. 环形链表
1 -> 2 -> 3 -> 4
^              |
|              v
7 <- 6 <- 5 <- 4

基本操作

  • 插入：在指定位置添加新节点
  • 删除：移除指定节点
  • 查找：遍历查找特定值
  • 反转：改变链表方向
  • 合并：将多个链表合并
  • 检测环：判断是否存在循环

应用场景

  • 动态内存分配
  • 实现队列/栈
  • LRU缓存系统
  • 多项式计算
  • 图的邻接表表示

经典问题

1. 反转链表

LeetCode 206 - Reverse Linked List

将链表反向的过程:

原始链表:
1 -> 2 -> 3 -> 4 -> NULL

反转过程:
1 -> 2 -> 3 -> 4 -> NULL
^
NULL <- 1    2 -> 3 -> 4
           ^
NULL <- 1 <- 2    3 -> 4
                ^
NULL <- 1 <- 2 <- 3    4
                     ^
NULL <- 1 <- 2 <- 3 <- 4
def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

2. 合并有序链表

LeetCode 21 - Merge Two Sorted Lists

合并过程示意:

输入:
l1: 1 -> 3 -> 5 -> NULL
l2: 2 -> 4 -> 6 -> NULL

步骤:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

3. 检测环

LeetCode 141 - Linked List Cycle

使用快慢指针检测环:

环形链表示例:
1 -> 2 -> 3 -> 4
     ^         |
     |         v
     7 <- 6 <- 5

检测过程:
第1步: 1 -> 2 -> 3 -> 4 -> 5
      s    f

第2步: 1 -> 2 -> 3 -> 4 -> 5
           s         f

第3步: 1 -> 2 -> 3 -> 4 -> 5
                s              f
def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

4. LRU缓存

LeetCode 146 - LRU Cache

使用双向链表和哈希表实现LRU缓存:

双向链表示例:
head <-> key1 <-> key2 <-> key3 <-> tail

访问key2后:
head <-> key1 <-> key3 <-> key2 <-> tail

插入key4，缓存满:
head <-> key3 <-> key2 <-> key4 <-> tail
class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head
    
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add(node)
            return node.value
        return -1
    
    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
        node = Node(key, value)
        self._add(node)
        self.cache[key] = node
        if len(self.cache) > self.capacity:
            node = self.head.next
            self._remove(node)
            del self.cache[node.key]
    
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def _add(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

常见技巧

  1. 使用哨兵节点（dummy node）简化头节点的处理
  2. 快慢指针解决环检测、中点查找等问题
  3. 多指针技术处理复杂的链表操作
  4. 递归和迭代两种方式实现链表操作
  5. 画图帮助理解复杂的链表操作

相关题目