链表
链表是一种动态数据结构，通过指针连接节点。与数组不同，链表不需要连续的内存空间，这使得插入和删除操作更加高效。掌握链表的操作对于 Microsoft SDE 面试非常重要。
链表基础
链表的特点
- 动态大小：可以动态添加和删除节点
- 非连续内存：节点在内存中不一定连续
- 插入删除高效：O(1) 时间插入和删除（已知位置）
- 随机访问低效：需要 O(n) 时间访问第 k 个元素
链表的类型
1. 单链表（Singly Linked List）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 创建链表
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
2. 双链表（Doubly Linked List）
class DoublyListNode:
def __init__(self, val=0, prev=None, next=None):
self.val = val
self.prev = prev
self.next = next
3. 循环链表（Circular Linked List）
# 循环单链表：最后一个节点的 next 指向头节点
# 循环双链表：最后一个节点的 next 指向头节点，头节点的 prev 指向最后一个节点
链表的基本操作
1. 遍历链表
def traverse(head):
current = head
while current:
print(current.val)
current = current.next
2. 查找节点
def find_node(head, target):
current = head
while current:
if current.val == target:
return current
current = current.next
return None
3. 插入节点
# 在头部插入
def insert_at_head(head, val):
new_node = ListNode(val)
new_node.next = head
return new_node
# 在指定位置后插入
def insert_after(prev_node, val):
if not prev_node:
return
new_node = ListNode(val)
new_node.next = prev_node.next
prev_node.next = new_node
4. 删除节点
# 删除指定值的节点
def delete_node(head, val):
dummy = ListNode(0)
dummy.next = head
current = dummy
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy.next
快慢指针技巧
快慢指针是处理链表问题的经典技巧，常用于：
- 检测链表中的环
- 找到链表的中间节点
- 找到链表的倒数第 k 个节点
- 判断链表是否为回文
1. 检测链表中的环
def has_cycle(head):
if not head or not head.next:
return False
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
2. 找到链表的中间节点
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
3. 找到链表的倒数第 k 个节点
def find_kth_from_end(head, k):
fast = slow = head
# 快指针先走 k 步
for _ in range(k):
if not fast:
return None
fast = fast.next
# 快慢指针同时移动
while fast:
slow = slow.next
fast = fast.next
return slow
常见题目
1. 反转链表
题目：反转一个单链表。
def reverse_list(head):
prev = None
current = head
while current:
next_temp = current.next
current.next = prev
prev = current
current = next_temp
return prev
2. 合并两个有序链表
题目：将两个升序链表合并为一个新的升序链表并返回。
def merge_two_lists(l1, l2):
dummy = ListNode(0)
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
3. 删除链表的倒数第 N 个节点
题目：给定一个链表，删除链表的倒数第 n 个节点，并返回链表的头结点。
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# 快指针先走 n+1 步
for _ in range(n + 1):
fast = fast.next
# 快慢指针同时移动
while fast:
slow = slow.next
fast = fast.next
# 删除节点
slow.next = slow.next.next
return dummy.next
4. 判断链表是否为回文
题目：判断一个链表是否为回文链表。
def is_palindrome(head):
# 找到中间节点
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 反转后半部分
prev = None
while slow:
next_temp = slow.next
slow.next = prev
prev = slow
slow = next_temp
# 比较前后两部分
while prev:
if head.val != prev.val:
return False
head = head.next
prev = prev.next
return True
5. 链表相交
题目：找到两个单链表相交的起始节点。
def get_intersection_node(headA, headB):
if not headA or not headB:
return None
pA, pB = headA, headB
# 当两个指针相遇或都到达末尾时停止
while pA != pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA
面试技巧
1. 使用虚拟头节点
虚拟头节点（dummy node）可以简化边界情况处理：
def remove_elements(head, val):
dummy = ListNode(0)
dummy.next = head
current = dummy
while current.next:
if current.next.val == val:
current.next = current.next.next
else:
current = current.next
return dummy.next
2. 注意边界情况
- 空链表
- 单个节点
- 两个节点
- 删除头节点或尾节点
3. 防止内存泄漏
在删除节点时，确保没有悬空指针：
# 正确做法
def delete_node(node):
node.val = node.next.val
node.next = node.next.next
# 注意：如果删除的是最后一个节点，需要特殊处理
总结
链表是算法面试中的重要数据结构：
- 掌握基本操作：遍历、查找、插入、删除
- 快慢指针：检测环、找中点、找倒数第 k 个节点
- 常见题目：反转、合并、删除、回文判断
- 面试技巧：使用虚拟头节点、注意边界情况
通过大量练习，你将能够熟练处理各种链表问题。
接下来，让我们学习栈与队列，这是两种重要的线性数据结构。