1. 反转单向链表
问题描述：将单向链表所有节点反转
思路：
使用三个指针：prev（前一个节点）、current（当前节点）、next_node（下一个节点）
遍历链表，每次将当前节点的next指向prev
移动三个指针直到链表末尾
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
prev = None
current = head
while current:
next_node = current.next # 保存下一个节点
current.next = prev # 反转指针
prev = current # 移动prev
current = next_node # 移动current
return prev # prev成为新的头节点
# 测试
# 创建链表: 1->2->3->4->5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5))))
# 反转链表
reversed_head = reverse_list(head)
# 打印结果: 5->4->3->2->1
current = reversed_head
while current:
print(current.val, end="->" if current.next else "")
current = current.next2. 检测链表中的环
问题描述：判断链表中是否存在环
思路（Floyd判圈算法/快慢指针）：
使用两个指针，slow每次移动一步，fast每次移动两步
如果存在环，fast最终会追上slow
如果fast遇到None，说明没有环
def has_cycle(head):
if not head or not head.next:
return False
slow = head
fast = head.next
while slow != fast:
if not fast or not fast.next:
return False # 到达链表尾部，无环
slow = slow.next
fast = fast.next.next
return True # slow == fast，存在环
# 测试
# 创建有环链表: 1->2->3->4->5->3 (5指向3)
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
node5.next = node3 # 形成环
print(has_cycle(node1)) # 输出: True
# 创建无环链表: 1->2->3->4->5
node5.next = None # 断开环
print(has_cycle(node1)) # 输出: False3. 合并两个有序链表
问题描述：合并两个升序链表为一个新的升序链表
思路：
创建哑节点(dummy)作为新链表的起点
比较两个链表的当前节点值
将较小值节点连接到新链表
当一个链表遍历完后，直接连接另一个链表的剩余部分
def merge_two_lists(l1, l2):
dummy = ListNode(-1) # 哑节点
current = dummy
while l1 and l2:
if l1.val <= l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next
# 连接剩余部分
current.next = l1 if l1 else l2
return dummy.next # 返回真正的头节点
# 测试
# 链表1: 1->3->5
l1 = ListNode(1, ListNode(3, ListNode(5)))
# 链表2: 2->4->6
l2 = ListNode(2, ListNode(4, ListNode(6)))
merged = merge_two_lists(l1, l2)
# 打印结果: 1->2->3->4->5->6
current = merged
while current:
print(current.val, end="->" if current.next else "")
current = current.next4. 数组与链表的优缺点比较
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存分配 | 连续内存块 | 分散内存，动态分配 |
| 随机访问 | O(1) - 通过索引直接访问 | O(n) - 需要遍历 |
| 插入/删除 | O(n) - 需要移动元素 | O(1) - 已知位置时 |
| 头部操作 | O(n) | O(1) |
| 尾部操作 | O(1) - 已知位置时 | O(1) - 有尾指针时 |
| 空间开销 | 仅存储数据 | 额外存储指针 |
| 缓存友好性 | 高 - 空间局部性好 | 低 - 内存不连续 |
| 大小调整 | 固定大小或昂贵扩容 | 动态调整大小 |
| 适用场景 | 随机访问频繁、数据量固定 | 频繁插入删除、数据量变化大 |
5. 实现LRU缓存（结合哈希表与双向链表）
LRU原理：最近最少使用策略，淘汰最久未使用的数据
数据结构：
双向链表：存储缓存条目，头部是最新使用的，尾部是最久未使用的
哈希表：O(1)时间访问任意节点
class DLinkedNode:
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.size = 0
# 使用哑节点简化操作
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _add_node(self, node):
"""添加节点到链表头部"""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
"""从链表中移除节点"""
prev = node.prev
next_node = node.next
prev.next = next_node
next_node.prev = prev
def _move_to_head(self, node):
"""移动节点到头部"""
self._remove_node(node)
self._add_node(node)
def _pop_tail(self):
"""移除尾部节点"""
node = self.tail.prev
self._remove_node(node)
return node
def get(self, key):
"""获取缓存值"""
node = self.cache.get(key)
if not node:
return -1
# 移动到头部表示最近使用
self._move_to_head(node)
return node.value
def put(self, key, value):
"""添加缓存"""
if key in self.cache:
# 更新值并移动到头部
node = self.cache[key]
node.value = value
self._move_to_head(node)
else:
# 创建新节点
node = DLinkedNode(key, value)
self.cache[key] = node
self._add_node(node)
self.size += 1
# 检查容量
if self.size > self.capacity:
# 移除尾部节点（最久未使用）
tail = self._pop_tail()
del self.cache[tail.key]
self.size -= 1
# 测试
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # 返回 1
cache.put(3, 3) # 淘汰 key 2
print(cache.get(2)) # 返回 -1 (未找到)
cache.put(4, 4) # 淘汰 key 1
print(cache.get(1)) # 返回 -1 (未找到)
print(cache.get(3)) # 返回 3
print(cache.get(4)) # 返回 46. 找出链表的中间节点
问题描述：返回链表的中间节点（偶数长度时返回第二个中间节点）
思路（快慢指针）：
slow每次移动一步，fast每次移动两步
当fast到达尾部时，slow正好在中间
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 测试
# 链表: 1->2->3->4->5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(middle_node(head).val) # 输出: 3
# 链表: 1->2->3->4->5->6
head.next.next.next.next.next = ListNode(6)
print(middle_node(head).val) # 输出: 4 (第二个中间节点)7. 判断链表是否为回文结构
问题描述：判断链表是否正序和倒序读都一样
思路：
找到中间节点（快慢指针）
反转后半部分链表
比较前半部分和反转后的后半部分
恢复链表（可选）
def is_palindrome(head):
if not head or not head.next:
return True
# 找到中间节点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分
second_half = reverse_list(slow)
# 比较两部分
first = head
second = second_half
result = True
while second and first:
if first.val != second.val:
result = False
break
first = first.next
second = second.next
# 恢复链表（可选）
reverse_list(second_half)
return result
# 测试
# 回文链表: 1->2->3->2->1
head = ListNode(1, ListNode(2, ListNode(3, ListNode(2, ListNode(1)))))
print(is_palindrome(head)) # 输出: True
# 非回文链表: 1->2->3->4->5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
print(is_palindrome(head)) # 输出: False8. 数组实现队列/栈 vs 链表实现
栈(Stack)实现比较
| 操作 | 数组实现 | 链表实现 |
|---|---|---|
| 入栈(push) | O(1) 摊还时间（动态数组） | O(1) |
| 出栈(pop) | O(1) | O(1) |
| 查看栈顶(peek) | O(1) | O(1) |
| 空间复杂度 | O(n) | O(n) |
| 优点 | 缓存友好，访问快 | 动态大小，无扩容开销 |
| 缺点 | 扩容开销大 | 每个元素额外指针空间 |
数组实现栈：
class ArrayStack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
return len(self.stack) == 0
def size(self):
return len(self.stack)链表实现栈：
class LinkedListStack:
def __init__(self):
self.top = None
def push(self, item):
new_node = ListNode(item)
new_node.next = self.top
self.top = new_node
def pop(self):
if self.top:
item = self.top.val
self.top = self.top.next
return item
return None
def peek(self):
if self.top:
return self.top.val
return None
def is_empty(self):
return self.top is None队列(Queue)实现比较
| 操作 | 数组实现 | 链表实现 |
|---|---|---|
| 入队(enqueue) | O(1) 摊还时间 | O(1) |
| 出队(dequeue) | O(n) - 需要移动元素 | O(1) |
| 查看队首(peek) | O(1) | O(1) |
| 空间复杂度 | O(n) | O(n) |
| 优点 | 缓存友好 | 高效出队操作 |
| 缺点 | 出队效率低 | 每个元素额外指针空间 |
循环数组实现队列（优化出队）：
class CircularQueue:
def __init__(self, capacity):
self.queue = [None] * capacity
self.capacity = capacity
self.front = 0
self.rear = 0
self.size = 0
def enqueue(self, item):
if self.is_full():
raise Exception("Queue is full")
self.queue[self.rear] = item
self.rear = (self.rear + 1) % self.capacity
self.size += 1
def dequeue(self):
if self.is_empty():
raise Exception("Queue is empty")
item = self.queue[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return item
def peek(self):
if self.is_empty():
return None
return self.queue[self.front]
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity链表实现队列：
class LinkedListQueue:
def __init__(self):
self.front = None
self.rear = None
def enqueue(self, item):
new_node = ListNode(item)
if self.rear is None:
self.front = self.rear = new_node
else:
self.rear.next = new_node
self.rear = new_node
def dequeue(self):
if self.front:
item = self.front.val
self.front = self.front.next
if self.front is None:
self.rear = None
return item
return None
def peek(self):
if self.front:
return self.front.val
return None
def is_empty(self):
return self.front is None总结建议：
栈实现选择：
需要高性能且数据量可预测 → 数组实现
数据量变化大或内存充足 → 链表实现
队列实现选择：
需要缓存友好且数据量固定 → 循环数组
数据量变化大或需要高效出队 → 链表实现