【LeetCode刷题指南特别篇】——移除链表元素，调试技巧，链表分割

在这篇特别篇中，我们将讨论几个链表相关的经典问题：移除链表元素、调试技巧和链表分割。这些是面试中常见的链表问题，掌握它们不仅能帮助你提升编程能力，还能提高解决链表相关问题的效率。

1. 移除链表元素

题目描述

给定一个链表的头节点head，以及一个目标值val，请你删除链表中所有的值为val的节点，并返回修改后的链表的头节点。

解题思路

这是链表问题中的常见题目，考察了链表的删除操作。可以通过以下几种方式实现：

  1. 虚拟头节点：为了处理删除的是头节点的情况，可以引入一个虚拟头节点来简化删除操作。
  2. 单遍历法：遍历链表，并在遍历过程中判断当前节点的值是否为目标值val，如果是，则删除该节点。

代码实现

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

def removeElements(head: ListNode, val: int) -> ListNode:
    # 创建虚拟头节点，防止删除头节点时出错
    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  # 返回去除虚拟头节点后的链表

解释

  1. dummy是一个虚拟节点，dummy.next指向原始链表的头节点。
  2. current用于遍历链表。若current.next.val == val，则删除该节点；否则，继续移动到下一个节点。
  3. 返回dummy.next，即去除虚拟头节点后的链表。

时间复杂度：O(n)，其中n是链表的节点数，最多遍历一遍链表。

空间复杂度：O(1)，使用了常数空间。

2. 调试技巧

在编写链表算法时，调试是非常重要的步骤。以下是一些常见的调试技巧：

1. 打印链表的内容

打印链表的内容非常重要，尤其是在复杂的链表操作中，能帮助你看到当前链表的状态。

def printList(head: ListNode):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("None")

2. 使用虚拟节点

如上面所提到的，在处理删除头节点或头节点特殊情况时，可以使用虚拟节点，它会让代码更加简洁和安全，减少判断条件。

3. 快慢指针调试

链表中涉及快慢指针的常见问题，尤其是在环检测、链表中点查找等问题中，使用快慢指针是非常有效的。

def detectCycle(head: ListNode) -> ListNode:
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:  # 相遇点
            break
    else:
        return None  # 没有环

    # 从头节点与相遇点同时开始，找到环的入口节点
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow  # 环的入口节点

4. 交替调试

链表的指针操作常常很容易出错。每次修改指针时，可以临时打印相关变量的值，观察是否按预期修改。

def reverseList(head: ListNode) -> ListNode:
    prev, curr = None, head
    while curr:
        print(f"prev: {prev}, curr: {curr.val}")  # 调试输出
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

3. 链表分割

题目描述

给定一个链表和一个值x，将链表按照小于x的节点、等于x的节点、大于x的节点进行三段分割，最后将这三段链表连接起来。

解题思路

将链表分成三部分，分别是小于x、等于x、大于x的部分。然后将这三部分链表连接起来。

  • 使用三个不同的链表（smaller, equal, greater）来保存三类节点。
  • 遍历原始链表，按值将节点加入对应的链表。
  • 最后将三个链表连接起来。

代码实现

def partition(head: ListNode, x: int) -> ListNode:
    smaller_head = smaller = ListNode(0)
    equal_head = equal = ListNode(0)
    greater_head = greater = ListNode(0)
    
    while head:
        if head.val < x:
            smaller.next = head
            smaller = smaller.next
        elif head.val == x:
            equal.next = head
            equal = equal.next
        else:
            greater.next = head
            greater = greater.next
        head = head.next
    
    greater.next = None  # 防止最后一个节点循环
    equal.next = greater_head.next
    smaller.next = equal_head.next
    
    return smaller_head.next

解释

  1. smaller_head, equal_head, 和 greater_head 分别是用于保存小于、等于和大于x的部分的链表头节点。
  2. 遍历链表，按值将每个节点加入对应的链表。
  3. 最后将这三段链表依次连接起来，并返回小于x部分的链表头。

时间复杂度：O(n)，其中n是链表的节点数，遍历一次链表。

空间复杂度：O(1)，只使用了常数空间。

总结

  • 移除链表元素：通过虚拟头节点简化删除操作，避免处理特殊情况。
  • 调试技巧：利用打印、虚拟节点、快慢指针等方法进行调试，帮助我们理解链表的操作。
  • 链表分割：将链表分成多个部分，按值进行分割，并将其重新连接。

这些是链表操作中常见的技巧和解法，希望能帮助你在刷题时提高效率！你有遇到相关问题需要解决吗？