LeetCode-链表问题解题技巧总结

VocabVictor2024-09-022024-09-04

引言

链表是一种常见的数据结构，在面试和实际编程中经常遇到。本文将总结链表的常见操作和解题技巧，帮助你更好地应对链表相关的算法问题。

1. 链表的基本结构

在开始之前，让我们先回顾一下链表的基本结构：

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

2. 常见链表操作

2.1 遍历链表

遍历是最基本的链表操作，也是许多其他操作的基础。

def traverse(head):
    current = head
    while current:
        print(current.val)
        current = current.next

2.2 插入节点

在链表中插入节点需要注意更新相关节点的指针。

def insert(head, val, position):
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    for _ in range(position):
        current = current.next
    new_node = ListNode(val)
    new_node.next = current.next
    current.next = new_node
    return dummy.next

2.3 删除节点

删除节点同样需要注意更新相关节点的指针。

def delete(head, position):
    dummy = ListNode(0)
    dummy.next = head
    current = dummy
    for _ in range(position):
        current = current.next
    current.next = current.next.next
    return dummy.next

3. 常见链表问题解题技巧

3.1 双指针技巧

双指针是解决链表问题的常用技巧，特别是在处理环形链表、找中点等问题时非常有用。

快慢指针

用于检测环、找中点等。

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

间隔指针

用于找倒数第 K 个节点等。

def findKthFromEnd(head, k):
    fast = slow = head
    for _ in range(k):
        if not fast:
            return None
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    return slow

3.2 反转链表

反转链表是一个常见的操作，也是很多复杂链表问题的基础。

def reverseList(head):
    prev = None
    current = head
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    return prev

3.3 合并链表

合并两个有序链表是另一个常见的操作。

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

4. 高级技巧

4.1 递归

很多链表问题可以用递归来解决，常见的包括反转链表、合并链表等。

def reverseListRecursive(head):
    if not head or not head.next:
        return head
    new_head = reverseListRecursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

4.2 虚拟头节点

使用虚拟头节点可以简化很多操作，特别是在需要修改头节点的情况下。

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