python实现反转部分单向链表

yipeiwu_com5年前Python基础

题目:

给定一个单链表的头指针 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设计】。

相关文章

10种检测Python程序运行时间、CPU和内存占用的方法

10种检测Python程序运行时间、CPU和内存占用的方法

在运行复杂的Python程序时,执行时间会很长,这时也许想提高程序的执行效率。但该怎么做呢? 首先,要有个工具能够检测代码中的瓶颈,例如,找到哪一部分执行时间比较长。接着,就针对这一部分...

学习和使用python的13个理由

学习和使用python的13个理由

如果您希望转向网站开发或软件开发,成为程序员中的一员,那么学习HTML,CSS和JavaScript的基础三重奏就不会出错。但要真正在拥挤的应用领域中脱颖而出,您还是需要学习其他编程语言...

python中time库的实例使用方法

time是python中处理时间的标准库 计算机时间的表达 提供获取系统时间并格式化输出功能 提供系统级精确计时功能,用于程序性能分析 用法:import time 函...

Python浅拷贝与深拷贝用法实例

本文实例讲述了Python浅拷贝与深拷贝用法。分享给大家供大家参考。具体分析如下: >>> person=['name',['savings',100]] >...

Pycharm新手教程(只需要看这篇就够了)

Pycharm新手教程(只需要看这篇就够了)

pycharm是一款高效的python IDE工具,它非常强大,且可以跨平台,是新手首选工具!下面我给第一次使用这款软件的朋友做一个简单的使用教程,希望能给你带来帮助! 目前pycha...