快捷導(dǎo)航

用python介紹4種常用的單鏈表翻轉(zhuǎn)的方法小結(jié)

更新時(shí)間：2020年02月24日 11:01:38 作者：petrolero

這篇文章主要介紹了用python介紹4種常用的單鏈表翻轉(zhuǎn)的方法小結(jié)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

如何把一個(gè)單鏈表進(jìn)行反轉(zhuǎn)？

方法1：將單鏈表儲(chǔ)存為數(shù)組，然后按照數(shù)組的索引逆序進(jìn)行反轉(zhuǎn)。

方法2：使用3個(gè)指針遍歷單鏈表，逐個(gè)鏈接點(diǎn)進(jìn)行反轉(zhuǎn)。

方法3：從第2個(gè)節(jié)點(diǎn)到第N個(gè)節(jié)點(diǎn)，依次逐節(jié)點(diǎn)插入到第1個(gè)節(jié)點(diǎn)(head節(jié)點(diǎn))之后，最后將第一個(gè)節(jié)點(diǎn)挪到新表的表尾。

方法4: 遞歸(相信我們都熟悉的一點(diǎn)是，對(duì)于樹的大部分問題，基本可以考慮用遞歸來解決。但是我們不太熟悉的一點(diǎn)是，對(duì)于單鏈表的一些問題，也可以使用遞歸。可以認(rèn)為單鏈表是一顆永遠(yuǎn)只有左(右)子樹的樹，因此可以考慮用遞歸來解決?；蛘哒f，因?yàn)閱捂湵肀旧淼慕Y(jié)構(gòu)也有自相似的特點(diǎn)，所以可以考慮用遞歸來解決)

開辟輔助數(shù)組，新建表頭反轉(zhuǎn)，就地反轉(zhuǎn)，遞歸反轉(zhuǎn)

# -*- coding: utf-8 -*-
'''
鏈表逆序
'''
class ListNode: 
  def __init__(self,x): 
    self.val=x
    self.next=None
 
'''
第一種方法：
對(duì)于一個(gè)長度為n的單鏈表head,用一個(gè)大小為n的數(shù)組arr儲(chǔ)存從單鏈表從頭
到尾遍歷的所有元素，在從arr尾到頭讀取元素簡歷一個(gè)新的單鏈表
時(shí)間消耗O(n),空間消耗O(n)
'''   
def reverse_linkedlist1(head):
  if head == None or head.next == None: #邊界條件
    return head
  arr = [] # 空間消耗為n,n為單鏈表的長度
  while head:
    arr.append(head.val)
    head = head.next
  newhead = ListNode(0)
  tmp = newhead
  for i in arr[::-1]:
    tmp.next = ListNode(i)
    tmp = tmp.next
  return newhead.next
 
'''
開始以單鏈表的第一個(gè)元素為循環(huán)變量cur,并設(shè)置2個(gè)輔助變量tmp,保存數(shù)據(jù);
newhead,新的翻轉(zhuǎn)鏈表的表頭。
時(shí)間消耗O(n),空間消耗O(1)
'''
 
def reverse_linkedlist2(head):
  if head == None or head.next == None: #邊界條件
    return head
  cur = head #循環(huán)變量
  tmp = None #保存數(shù)據(jù)的臨時(shí)變量
  newhead = None #新的翻轉(zhuǎn)單鏈表的表頭
  while cur:
    tmp = cur.next
    cur.next = newhead
    newhead = cur  # 更新 新鏈表的表頭
    cur = tmp
  return newhead
   
'''
開始以單鏈表的第二個(gè)元素為循環(huán)變量，用2個(gè)變量循環(huán)向后操作,并設(shè)置1個(gè)輔助變量tmp,保存數(shù)據(jù);
時(shí)間消耗O(n),空間消耗O(1)
'''
 
 
def reverse_linkedlist3(head):
  if head == None or head.next == None: #邊界條件
    return head
  p1 = head #循環(huán)變量1
  p2 = head.next #循環(huán)變量2
  tmp = None #保存數(shù)據(jù)的臨時(shí)變量
  while p2:
    tmp = p2.next
    p2.next = p1
    p1 = p2
    p2 = tmp
  head.next = None
  return p1
 
'''
遞歸操作，先將從第一個(gè)點(diǎn)開始翻轉(zhuǎn)轉(zhuǎn)換從下一個(gè)節(jié)點(diǎn)開始翻轉(zhuǎn)
直至只剩一個(gè)節(jié)點(diǎn)
時(shí)間消耗O(n),空間消耗O(1)
'''
 
def reverse_linkedlist4(head):
  if head is None or head.next is None:
    return head
  else:
    newhead=reverse_linkedlist4(head.next)
    head.next.next=head
    head.next=None
  return newhead
 
     
def create_ll(arr):
  pre = ListNode(0)
  tmp = pre
  for i in arr:
    tmp.next = ListNode(i)
    tmp = tmp.next
  return pre.next
   
def print_ll(head):
  tmp = head
  while tmp:
    print tmp.val
    tmp=tmp.next
 
a = create_ll(range(5))
print_ll(a) # 0 1 2 3 4
a = reverse_linkedlist1(a)
print_ll(a) # 4 3 2 1 0
a = reverse_linkedlist2(a)
print_ll(a) # 0 1 2 3 4
a = reverse_linkedlist3(a)
print_ll(a) # 4 3 2 1 0
a = reverse_linkedlist4(a)
print_ll(a) # 0 1 2 3 4

到此這篇關(guān)于用python介紹4種常用的單鏈表翻轉(zhuǎn)的方法小結(jié)的文章就介紹到這了,更多相關(guān)python 單鏈表翻轉(zhuǎn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: