单链表（Singly Linked List）是数据结构中的一种常见形式，其特点是每个节点包含数据和指向下一个节点的指针。在处理单链表的算法题时，有一些常见的技巧和套路可以帮助我们更高效地解决问题。以下是一些常见的技巧和套路：

1.双指针技巧

双指针技巧是解决单链表问题的常用方法，尤其是在处理链表中的环、中点、倒数第k个节点等问题时非常有效。

o 快慢指针（龟兔赛跑算法）：

o 应用场景：判断链表是否有环、找到链表的中间节点、找到环的入口点等。

o 实现方式：使用两个指针，一个快指针（每次移动两步）和一个慢指针（每次移动一步）。如果链表有环，快指针最终会追上慢指针。

o 示例代码：

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

o 前后指针：

o 应用场景：删除链表的倒数第k个节点、找到链表的倒数第k个节点等。

o 实现方式：使用两个指针，一个先移动k步，然后两个指针同时移动，直到先移动的指针到达链表末尾。

o 示例代码：

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    first = second = dummy
    for _ in range(n + 1):
        first = first.next
    while first:
        first = first.next
        second = second.next
    second.next = second.next.next
    return dummy.next

2.虚拟头节点（Dummy Node）

虚拟头节点技巧可以简化链表操作，尤其是在处理头节点的删除、插入等操作时，避免对头节点的特殊处理。

o 应用场景：删除链表中的节点、合并两个有序链表、反转链表等。

o 实现方式：在链表头部添加一个虚拟节点，使得头节点的操作与其他节点一致。

o 示例代码：

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.反转链表

反转链表是单链表问题中的经典操作，常用于解决回文链表、链表逆序等问题。

o 应用场景：反转整个链表、反转链表的一部分、判断链表是否为回文链表等。

o 实现方式：使用三个指针（prev, current, next）来逐个反转链表中的节点。

o 示例代码：

def reverse_list(head):
  prev = None
  current = head
  while current:
      next_node = current.next
      current.next = prev
      prev = current
      current = next_node
  return prev

4.链表合并与分割

链表的合并与分割是常见的操作，尤其是在处理多个链表时。

o 应用场景：合并两个有序链表、分割链表（如将链表分为小于某个值和大于某个值的两部分）等。

o 实现方式：使用指针逐个比较和连接节点。

o 示例代码：

def partition(head, x):
  before = before_head = ListNode(0)
  after = after_head = ListNode(0)
  while head:
      if head.val < x:
          before.next = head
          before = before.next
      else:
          after.next = head
          after = after.next
      head = head.next
  after.next = None
  before.next = after_head.next
  return before_head.next

5.递归与迭代

递归和迭代是解决链表问题的两种基本方法，各有优缺点。

o 递归：

o 优点：代码简洁，易于理解。

o 缺点：递归深度过大时可能导致栈溢出。

o 应用场景：反转链表、合并链表、判断回文链表等。

o 示例代码：

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    p = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return p

o 迭代：

o 优点：效率高，不会出现栈溢出问题。

o 缺点：代码相对复杂。

o 应用场景：反转链表、删除节点、合并链表等。

o 示例代码：

def reverse_list_iterative(head):
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev

6.链表的环检测与入口点查找

链表的环检测和环入口点查找是常见的面试题，通常使用快慢指针来解决。

o 应用场景：判断链表是否有环、找到环的入口点。

o 实现方式：使用快慢指针找到相遇点，然后通过数学推导找到环的入口点。

o 示例代码：

def detect_cycle(head):
  slow = fast = head
  while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow == fast:
          break
  else:
      return None
  while head != slow:
      head = head.next
      slow = slow.next
  return head

7.链表的排序

链表的排序通常使用归并排序，因为链表的特性使得归并排序的空间复杂度为O(1)。

o 应用场景：对链表进行排序。

o 实现方式：使用快慢指针找到链表中点，然后递归合并两个有序链表。

o 示例代码：

def sort_list(head):
  if not head or not head.next:
      return head
  slow, fast = head, head.next
  while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
  mid = slow.next
  slow.next = None
  return merge(sort_list(head), sort_list(mid))

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

总结

单链表问题的解决通常依赖于双指针、虚拟头节点、递归与迭代等技巧。掌握这些常见的套路可以帮助我们更高效地解决链表相关的问题。在实际应用中，根据具体问题的特点选择合适的技巧和方法是关键。

如果你觉得有用的话，帮忙一键三联。

毕竟：我太想进步了

Tags：设指针变量p指向单链表中结点a

微信扫一扫：分享

微信里点“发现”，扫一下

二维码便可将本文分享至朋友圈。