链表高频面试题有哪些？

# 迭代法（三指针） def reverse_list(head): prev = None curr = head while curr: next_temp = curr.next # 保存下一个 curr.next = prev # 反转 prev = curr # 移动 prev curr = next_temp # 移动 curr return prev # 递归法 def reverse_list_recursive(head): if not head or not head.next: return head new_head = reverse_list_recursive(head.next) head.next.next = head # 反转 head.next = None return new_head

def merge_two_lists(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

# 判断是否有环（快慢指针） def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False # 找到入环点 def detect_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # 相遇 # 从头和相遇点同时走，再次相遇就是入环点 ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptr return None # 原理： # 设头到入环点距离 a，入环点到相遇点距离 b，相遇点到入环点距离 c # 慢指针走 a+b，快指针走 a+b+n(b+c) # 快指针速度是慢指针 2 倍：2(a+b) = a+b+n(b+c) # → a = (n-1)(b+c) + c # → 从头走 a 步 = 从相遇点走 c + n-1 圈 → 在入环点相遇

def remove_nth_from_end(head, n): dummy = ListNode(0, head) fast = slow = dummy # fast 先走 n+1 步 for _ in range(n + 1): fast = fast.next # fast 和 slow 同时走 while fast: fast = fast.next slow = slow.next # slow 指向倒数第 n+1 个节点 slow.next = slow.next.next return dummy.next

def reverse_k_group(head, k): # 检查是否有 k 个节点 curr = head count = 0 while curr and count < k: curr = curr.next count += 1 if count < k: return head # 反转前 k 个 prev = None curr = head for _ in range(k): next_temp = curr.next curr.next = prev prev = curr curr = next_temp # head 变成尾节点，连接下一组 head.next = reverse_k_group(curr, k) return prev # prev 是新的头节点

def sort_list(head): if not head or not head.next: return head # 快慢指针找中点 slow, fast = head, head.next while fast and fast.next: slow = slow.next fast = fast.next.next mid = slow.next slow.next = None # 断开 left = sort_list(head) right = sort_list(mid) return merge_two_lists(left, right)

class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = {} # key → Node # 双向链表：head ↔ ... ↔ tail self.head = Node(0, 0) # 哨兵头 self.tail = Node(0, 0) # 哨兵尾 self.head.next = self.tail self.tail.prev = self.head def get(self, key): if key not in self.cache: return -1 node = self.cache[key] self._move_to_head(node) # 移到头部 return node.val def put(self, key, value): if key in self.cache: node = self.cache[key] node.val = value self._move_to_head(node) else: node = Node(key, value) self.cache[key] = node self._add_to_head(node) if len(self.cache) > self.cap: removed = self._remove_tail() del self.cache[removed.key]