链表与数组面试常见问题详解与实现

1. 反转单向链表

问题描述：将单向链表所有节点反转

思路：

1. 使用三个指针：prev（前一个节点）、current（当前节点）、next_node（下一个节点）

2. 遍历链表，每次将当前节点的next指向prev

3. 移动三个指针直到链表末尾

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef reverse_list(head):prev = Nonecurrent = headwhile current:next_node = current.next  # 保存下一个节点current.next = prev       # 反转指针prev = current            # 移动prevcurrent = next_node       # 移动currentreturn 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判圈算法/快慢指针）：

1. 使用两个指针，slow每次移动一步，fast每次移动两步

2. 如果存在环，fast最终会追上slow

3. 如果fast遇到None，说明没有环

def has_cycle(head):if not head or not head.next:return Falseslow = headfast = head.nextwhile slow != fast:if not fast or not fast.next:return False  # 到达链表尾部，无环slow = slow.nextfast = fast.next.nextreturn 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. 合并两个有序链表

问题描述：合并两个升序链表为一个新的升序链表

思路：

1. 创建哑节点(dummy)作为新链表的起点

2. 比较两个链表的当前节点值

3. 将较小值节点连接到新链表

4. 当一个链表遍历完后，直接连接另一个链表的剩余部分

def merge_two_lists(l1, l2):dummy = ListNode(-1)  # 哑节点current = dummywhile l1 and l2:if l1.val <= l2.val:current.next = l1l1 = l1.nextelse:current.next = l2l2 = l2.nextcurrent = current.next# 连接剩余部分current.next = l1 if l1 else l2return 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. 数组与链表的优缺点比较

5. 实现LRU缓存（结合哈希表与双向链表）

LRU原理：最近最少使用策略，淘汰最久未使用的数据

数据结构：

• 双向链表：存储缓存条目，头部是最新使用的，尾部是最久未使用的

• 哈希表：O(1)时间访问任意节点

class DLinkedNode:def __init__(self, key=0, value=0):self.key = keyself.value = valueself.prev = Noneself.next = Noneclass LRUCache:def __init__(self, capacity):self.capacity = capacityself.cache = {}self.size = 0# 使用哑节点简化操作self.head = DLinkedNode()self.tail = DLinkedNode()self.head.next = self.tailself.tail.prev = self.headdef _add_node(self, node):"""添加节点到链表头部"""node.prev = self.headnode.next = self.head.nextself.head.next.prev = nodeself.head.next = nodedef _remove_node(self, node):"""从链表中移除节点"""prev = node.prevnext_node = node.nextprev.next = next_nodenext_node.prev = prevdef _move_to_head(self, node):"""移动节点到头部"""self._remove_node(node)self._add_node(node)def _pop_tail(self):"""移除尾部节点"""node = self.tail.prevself._remove_node(node)return nodedef get(self, key):"""获取缓存值"""node = self.cache.get(key)if not node:return -1# 移动到头部表示最近使用self._move_to_head(node)return node.valuedef put(self, key, value):"""添加缓存"""if key in self.cache:# 更新值并移动到头部node = self.cache[key]node.value = valueself._move_to_head(node)else:# 创建新节点node = DLinkedNode(key, value)self.cache[key] = nodeself._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. 找出链表的中间节点

问题描述：返回链表的中间节点（偶数长度时返回第二个中间节点）

思路（快慢指针）：

1. slow每次移动一步，fast每次移动两步

2. 当fast到达尾部时，slow正好在中间

def middle_node(head):slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextreturn 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. 判断链表是否为回文结构

问题描述：判断链表是否正序和倒序读都一样

思路：

1. 找到中间节点（快慢指针）

2. 反转后半部分链表

3. 比较前半部分和反转后的后半部分

4. 恢复链表（可选）

def is_palindrome(head):if not head or not head.next:return True# 找到中间节点slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.next# 反转后半部分second_half = reverse_list(slow)# 比较两部分first = headsecond = second_halfresult = Truewhile second and first:if first.val != second.val:result = Falsebreakfirst = first.nextsecond = 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)实现比较

数组实现栈：

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 Nonedef peek(self):if not self.is_empty():return self.stack[-1]return Nonedef is_empty(self):return len(self.stack) == 0def size(self):return len(self.stack)

链表实现栈：

class LinkedListStack:def __init__(self):self.top = Nonedef push(self, item):new_node = ListNode(item)new_node.next = self.topself.top = new_nodedef pop(self):if self.top:item = self.top.valself.top = self.top.nextreturn itemreturn Nonedef peek(self):if self.top:return self.top.valreturn Nonedef is_empty(self):return self.top is None

队列(Queue)实现比较

循环数组实现队列（优化出队）：

class CircularQueue:def __init__(self, capacity):self.queue = [None] * capacityself.capacity = capacityself.front = 0self.rear = 0self.size = 0def enqueue(self, item):if self.is_full():raise Exception("Queue is full")self.queue[self.rear] = itemself.rear = (self.rear + 1) % self.capacityself.size += 1def dequeue(self):if self.is_empty():raise Exception("Queue is empty")item = self.queue[self.front]self.front = (self.front + 1) % self.capacityself.size -= 1return itemdef peek(self):if self.is_empty():return Nonereturn self.queue[self.front]def is_empty(self):return self.size == 0def is_full(self):return self.size == self.capacity

链表实现队列：

class LinkedListQueue:def __init__(self):self.front = Noneself.rear = Nonedef enqueue(self, item):new_node = ListNode(item)if self.rear is None:self.front = self.rear = new_nodeelse:self.rear.next = new_nodeself.rear = new_nodedef dequeue(self):if self.front:item = self.front.valself.front = self.front.nextif self.front is None:self.rear = Nonereturn itemreturn Nonedef peek(self):if self.front:return self.front.valreturn Nonedef is_empty(self):return self.front is None

总结建议：

• 栈实现选择：

  • 需要高性能且数据量可预测 → 数组实现

  • 数据量变化大或内存充足 → 链表实现

• 队列实现选择：

  • 需要缓存友好且数据量固定 → 循环数组

  • 数据量变化大或需要高效出队 → 链表实现