链表算法精讲：从基础到高频面试题

链表是最基础也是最重要的数据结构之一，在面试中出现频率极高。本文将深入讲解链表的核心算法思想，并通过实际代码演示如何解决常见的链表问题。

一、链表基础与核心思想

1.1 链表的结构特点

链表是一种动态数据结构，相比数组具有以下优势：

• 动态大小：不需要预先分配固定大小的内存
• 高效插入删除：在已知位置插入删除的时间复杂度为O(1)
• 内存利用灵活：可以分散存储，不要求连续内存

但链表也有劣势：

• 随机访问慢：访问第n个元素需要O(n)时间
• 额外空间开销：每个节点需要存储指针信息

1.2 链表的基本操作

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# 遍历链表
def traverse_linked_list(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result
​

二、经典链表算法

2.1 反转链表

反转链表是最经典的链表问题，掌握迭代和递归两种解法非常重要。

迭代解法：

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    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
​

算法分析：

• 时间复杂度：O(n)
• 空间复杂度：迭代O(1)，递归O(n)（递归栈深度）

2.2 快慢指针法

快慢指针是解决链表问题的核心技巧，一个指针每次走一步，另一个指针每次走两步。

应用场景：

1. 寻找链表中点
2. 判断链表是否有环
3. 寻找环的入口
4. 寻找倒数第k个节点

判断链表是否有环：

def has_cycle(head):
    if not head or not head.next:
        return False
    slow, fast = head, head.next
    while fast and fast.next:
        if slow == fast:
            return True
        slow = slow.next
        fast = fast.next.next
    return False
​

寻找链表中点：

def find_middle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow
​

2.3 合并有序链表

合并两个有序链表是归并排序的基础，也是高频面试题。

迭代解法：

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
​

递归解法：

def merge_two_lists_recursive(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    
    if l1.val <= l2.val:
        l1.next = merge_two_lists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_two_lists_recursive(l1, l2.next)
        return l2
​

三、高频面试题精讲

3.1 删除链表的倒数第N个节点

题目：给定一个链表，删除链表的倒数第n个节点，并且返回链表的头结点。

解法思路：

1. 使用快慢指针，快指针先走n步
2. 然后快慢指针同时移动，直到快指针到达末尾
3. 此时慢指针的下一个节点就是要删除的节点

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast, slow = dummy, 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
​

3.2 判断回文链表

题目：判断一个链表是否为回文链表。

解法思路：

1. 使用快慢指针找到链表中点
2. 反转后半部分链表
3. 比较前后两半是否相同
4. 恢复链表（可选）

def is_palindrome(head):
    if not head or not head.next:
        return True
    
    # 找到中点
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 反转后半部分
    second_half = reverse_list(slow)
    
    # 比较
    first, second = head, second_half
    result = True
    while second:
        if first.val != second.val:
            result = False
            break
        first = first.next
        second = second.next
    
    # 恢复链表
    reverse_list(second_half)
    return result
​

3.3 环形链表II

题目：给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null。

数学原理：
设链表头到环入口距离为a，环入口到相遇点距离为b，相遇点到环入口距离为c。
相遇时：快指针路程 = a + b + c + b = a + 2b + c
慢指针路程 = a + b
由于快指针速度是慢指针2倍，所以：2(a + b) = a + 2b + c
解得：a = c

def detect_cycle(head):
    if not head or not head.next:
        return None
    
    # 判断是否有环并找到相遇点
    slow, fast = head, head
    has_cycle = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # 找到环的入口
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow
​

四、进阶技巧

4.1 哨兵节点技巧

在处理链表头节点可能变化的问题时，使用哨兵节点可以简化代码逻辑。

def partition(head, x):
    dummy = ListNode(0)
    dummy.next = head
    
    # 创建小于x和大于等于x的两个链表
    less_dummy, greater_dummy = ListNode(0), ListNode(0)
    less, greater = less_dummy, greater_dummy
    
    current = head
    while current:
        if current.val < x:
            less.next = current
            less = less.next
        else:
            greater.next = current
            greater = greater.next
        current = current.next
    
    # 连接两个链表
    less.next = greater_dummy.next
    greater.next = None
    
    return less_dummy.next
​

4.2 链表排序

对链表排序的推荐方法是归并排序，时间复杂度O(n log n)。

def sort_list(head):
    if not head or not head.next:
        return head
    
    # 分割链表
    mid = find_middle(head)
    right = mid.next
    mid.next = None
    
    # 递归排序
    left = sort_list(head)
    right = sort_list(right)
    
    # 合并
    return merge_two_lists(left, right)
​

五、总结与建议

掌握链表算法的关键要点：

1. 基础扎实：熟练掌握链表的基本操作和指针操作
2. 多画图：链表问题比较抽象，画图能帮助理解
3. 注意边界：空链表、单节点、头尾节点等特殊情况
4. 灵活应用：快慢指针、哨兵节点、递归等技巧的灵活运用
5. 代码规范：注意内存管理，避免内存泄漏

链表算法是面试中的必考内容，建议通过大量练习来提高熟练度。从简单的反转、合并开始，逐步掌握复杂的环形问题、排序问题，最终能够熟练运用各种技巧解决实际问题。