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.next
2. 检测链表中的环
问题描述:判断链表中是否存在环
思路(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)) # 输出: False
3. 合并两个有序链表
问题描述:合并两个升序链表为一个新的升序链表
思路:
创建哑节点(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.next
4. 数组与链表的优缺点比较
特性 | 数组 | 链表 |
---|---|---|
内存分配 | 连续内存块 | 分散内存,动态分配 |
随机访问 | 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)) # 返回 4
6. 找出链表的中间节点
问题描述:返回链表的中间节点(偶数长度时返回第二个中间节点)
思路(快慢指针):
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)) # 输出: False
8. 数组实现队列/栈 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
总结建议:
栈实现选择:
需要高性能且数据量可预测 → 数组实现
数据量变化大或内存充足 → 链表实现
队列实现选择:
需要缓存友好且数据量固定 → 循环数组
数据量变化大或需要高效出队 → 链表实现