Python实现单向链表指定区间反转算法解析

沈知远

发布时间：2026-10-13| 6人浏览过

原创

本文介绍如何使用Python反转单向链表中指定索引区间[a, b]的节点。通过遍历计算链表长度并处理边界情况，利用指针重定向实现局部反转。算法时间复杂度为O(n)，空间复杂度为O(1)，适用于需要局部调整链表结构的场景。

题目要求：

给定一个单向链表的头指针 head，以及两个整数 a 和 b，需要在单链表中反转索引范围从 a 到 b 的节点，最后返回整个链表的头指针。例如，对于单链表 [1000, 5, 12, 100, 45, 'cecil', 999]，当 a = 4，b = 6 时，返回的链表应为 [1000, 5, 12, 100, 999, 'cecil', 45]。这里 a 和 b 代表索引值，若 a 或 b 超出索引范围，则返回错误信息。

代码实现：

作者编写的代码虽然逻辑可行，但结构较为繁琐。主要原因是使用了 for 循环处理反转逻辑，导致在 a == 0 的特殊情况下，for 循环无法直接识别和处理，需要额外分支处理。

  def reverse_part_linked_list(head, a, b): # 反转部分链表结点，a, b分别为索引值
    if head == 0:
      print "Empty linked list. No need to reverse."
      return head
    p = head
    length = 1
    while p != 0:
      length += 1
      p = p.next
    if length == 1:
      print "No need to reverse."
      return head
    if a < 0 or b > length-1 or a >= b:
      raise Exception("The given 'from' value and 'to' value is wrong.")
    p = head

    if a == 0: # 由于 for 循环中 xrange 的范围问题，我就分情况写了。
      tail, head = p, p
      pre = 0
      for _ in xrange(a, b+1):
        p = p.next
        head.next = pre
        pre = head
        head = p
      tail.next = p
      return head
    else:
      for _ in xrange(1, a):
        p = p.next
      front, tail, head = p, p, p
      p = p.next
      pre = 0
      for _ in xrange(a+1, b+2):
        p = p.next
        head.next = pre
        pre = head
        head = p
      front.next = pre
      tail.next = p
      return head

逻辑分析：

核心问题在于反转链表时的指针指向调整。整个算法仅需一次遍历，时间复杂度为 O(n)，空间复杂度仅涉及几个辅助变量，保持为 O(1)。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。