LeetCode 500 题攻略：高频算法问题解析

在 LeetCode 平台上，共有超过 500 道编程挑战题目，这些题目覆盖了从基础到高级的各类算法问题。以下将针对其中几个高频出现的问题进行详细解析，帮助读者在备战面试或提升编程能力时能够有的放矢。

问题一：如何高效实现链表反转？

链表反转是数据结构中的基础操作，它有多种实现方式。以下是一种常用的迭代方法：

定义一个哑节点 dummy 作为头节点的前一个节点。

初始化三个指针：pre 指向 dummy，cur 指向 head，next 指向 cur 的下一个节点。

循环遍历链表，每次将 cur 的下一个节点指向 pre，然后移动 pre 和 cur 指针向前。

当 cur 为空时，pre 将指向新的头节点。

以下是相关代码示例：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def reverseList(head):
    dummy = ListNode(0)
    pre = dummy
    cur = head
    while cur:
        next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    return pre

问题二：如何在不使用额外空间的情况下实现两个数组的交集？

在不使用额外空间的情况下实现两个数组的交集，可以通过双指针的方法来解决问题。以下是具体步骤：

对两个数组进行排序。

初始化两个指针，分别指向两个数组的起始位置。

比较两个指针指向的元素，如果相等，则将结果加入到一个新的列表中，并移动两个指针。

如果当前指针指向的元素小于另一个数组的元素，则移动较小的指针。

如果当前指针指向的元素大于另一个数组的元素，则移动较大的指针。

重复步骤 3-5，直到任一指针超出数组的范围。

以下是相关代码示例：

def intersection(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    result = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            result.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return result

问题三：如何实现一个高效的字符串匹配算法？

字符串匹配算法是计算机科学中常见的问题，KMP 算法是一种高效的处理字符串匹配的方法。以下是 KMP 算法的基本思想：

构建一个部分匹配表（也称为“前缀表”），该表记录了模式串中任意前缀的最长相同前后缀的长度。

在匹配过程中，如果发生不匹配，则利用部分匹配表确定下一次比较的位置，避免从头开始比较。

以下是 KMP 算法的部分匹配表构建和匹配过程的代码示例：

def kmp_search(s, p):
    def build_partial_match_table(p):
        m = len(p)
        lps = [0]  m
        length = 0
        i = 1
        while i < m:
            if p[i] == p[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
    lps = build_partial_match_table(p)
    i, j = 0, 0
    while i < len(s):
        if p[j] == s[i]:
            i += 1
            j += 1
        if j == len(p):
            return i j
        elif i < len(s) and p[j] != s[i]:
            if j != 0:
                j = lps[j 1]
            else:
                i += 1
    return -1