python实现反转部分单向链表

Dulcea ·

更新时间:2024-11-15

· 735 次阅读

题目：

给定一个单链表的头指针 head，以及两个整数 a 和 b，在单链表中反转 linked_list[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），空间复杂度为若干个变量。

您可能感兴趣的文章:python双向链表实现实例代码Python二叉搜索树与双向链表转换实现方法Python单向链表和双向链表原理与用法实例详解Python数据结构之双向链表的定义与使用方法示例Python二叉搜索树与双向链表转换算法示例Python双向循环链表实现方法分析浅谈Python单向链表的实现python数据结构链表之单向链表(实例讲解)python实现单向链表详解Python实现的单向循环链表功能示例python单向链表的基本实现与使用方法【定义、遍历、添加、删除、查找等】python双向链表原理与实现方法详解

单向链表反转链表 Python

1024 个赞