python實(shí)現(xiàn)反轉(zhuǎn)部分單向鏈表

發(fā)布時(shí)間：2020-09-15 04:17:00 來源：腳本之家閱讀：278 作者：冬日新雨欄目：開發(fā)技術(shù)

題目：

給定一個(gè)單鏈表的頭指針 head，以及兩個(gè)整數(shù) a 和 b，在單鏈表中反轉(zhuǎn) linked_list[a-b] 的結(jié)點(diǎn)，然后返回整個(gè)鏈表的頭指針。
例如：
單鏈表[1000, 5, 12, 100, 45, ‘cecil', 999]，
a = 4， b = 6，
返回的鏈表是[1000, 5, 12, 100, 999, ‘cecil', 45]，也就是說，
a 和 b分別為索引值。如果a 和 b 超過了索引范圍就返回錯(cuò)誤。

代碼：

我寫的不夠簡潔，比較繁瑣，但是能跑通，繁瑣的原因在于我使用了 for 循環(huán)，對于 a == 0 的情況 for 循環(huán)無法識別。

  def reverse_part_linked_list(head, a, b): # 反轉(zhuǎn)部分鏈表結(jié)點(diǎn)，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 循環(huán)中 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

分析：

核心依然是反轉(zhuǎn)鏈表的指針問題，均是一遍循環(huán)，時(shí)間復(fù)雜度o（n），空間復(fù)雜度為若干個(gè)變量。

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。

向AI問一下細(xì)節(jié)

python實(shí)現(xiàn)反轉(zhuǎn)部分單向鏈表

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽