欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python反轉單鏈表算法題

 更新時間:2022年05月05日 08:28:09   作者:小小小小人ksh  
這篇文章主要為大家詳細介紹了python反轉單鏈表算法題,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下

現(xiàn)在算法是大廠面試的必考題,而且越來越難,已經(jīng)不是簡單的列表,字符串操作了,會涉及到各種數(shù)據(jù)結結構。單鏈表的反轉也是經(jīng)??嫉囊坏李},里面故在此記錄一下。

1.鏈表的特點:

順序存儲元素,但是元素在空間上是不連續(xù)的,所以在鏈表每個元素中除了存儲元素的值,還會存儲下一個元素的地址,單鏈表的話就只有指向下一個元素的指針,雙向鏈表的話還會有指向前一個元素的指針。正是由于鏈表以上的存儲特點,在做插入和刪除操作時只需要斷開指針的連接,不需要移動后面的數(shù)據(jù),所以對鏈表修改的效率會很高,但是查找的效率會很低,這也正是鏈表和數(shù)組的區(qū)別。鏈表的存儲示意圖:

完成這道題至少有3種方式:

1.先對原鏈表做頭部刪操作,再對新鏈表做頭部插入操作;
2.通過3個指針實現(xiàn),p0指向前一個節(jié)點的指針,p1表示當前節(jié)點的指針,p2表示下一個節(jié)點的指針
3.用遞歸實現(xiàn);

2.方式一:

1)創(chuàng)建一個新的空列表;

2)取出舊鏈表中頭結點的元素,將其next指針設置為新鏈表的頭指針,同時將舊鏈表的頭結點執(zhí)行下一個元素

3)依次重復第2)步的操作,直到取出就鏈表中所有的節(jié)點。

4)最后形成的新鏈表如下,實現(xiàn)了反轉的功能:

5)代碼實現(xiàn):

# encoding=utf-8
import copy
?
?
class Node:
? ? """節(jié)點類,包含值和下一個節(jié)點的指針"""
? ? def __init__(self, value, next=None):
? ? ? ? self.value = value
? ? ? ? self.next = next
?
? ? def __str__(self):
? ? ? ? return "Node value:%s" % self.value
?
?
class LinkedList:
? ? def __init__(self, head=None, tail=None):
? ? ? ? self.head = head
? ? ? ? self.tail = tail
?
? ? def get_all(self):
? ? ? ? """獲取鏈表中所有的節(jié)點"""
? ? ? ? nodes = []
? ? ? ? temp = self.head
? ? ? ? while temp:
? ? ? ? ? ? nodes.append(temp.value)
? ? ? ? ? ? temp = temp.next
? ? ? ? return nodes
?
? ? def add_node(self, value):
? ? ? ? """在列表中添加節(jié)點"""
? ? ? ? node = Node(value)
? ? ? ? # 空鏈表,收尾指針都指向新增加的節(jié)點
? ? ? ? if self.head is None:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? else:
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
?
? ? def reverse_list(self):
? ? ? ? """反轉單向列表
? ? ? ? 思路一:先對原鏈表做頭刪操作,再對新鏈表做頭插
? ? ? ? """
? ? ? ? # 定義一個新的鏈表
? ? ? ? new_list_node = LinkedList()
? ? ? ? temp = copy.deepcopy(self.head)
? ? ? ? while temp:
? ? ? ? ? ? # 1.對之前的鏈表做頭刪除操作
? ? ? ? ? ? node = temp
? ? ? ? ? ? temp = temp.next
?
? ? ? ? ? ? # 2.對新的鏈表做頭插入操作
? ? ? ? ? ? if new_list_node.head is None:
? ? ? ? ? ? ? ? new_list_node.tail = node
? ? ? ? ? ? node.next = new_list_node.head
? ? ? ? ? ? new_list_node.head = node
? ? ? ? return new_list_node
?
?
if __name__ == "__main__":
? ? l = LinkedList()
? ? for i in range(5):
? ? ? ? l.add_node(i)
? ? new_list_node = l.reverse_list()
? ? print(new_list_node.get_all())
? ? print(new_list_node.tail)

3.方式二

借助3個指針來實現(xiàn)反轉,p0之前前一個節(jié)點,p1指向當前操作的節(jié)點,p2指向下一個節(jié)點。操作過程如下:將p1的next指針之前p0,之后將p0指向p1節(jié)點,p1指向p2節(jié)點,如果p1不為空,重復以上操作,最后,p0即為新列表的頭節(jié)點。

1)開始時p0為空;將p1指向鏈表的頭節(jié)點,p1節(jié)點的next指針指向p0;p2指向下一個節(jié)點:

2)調整3個指針的指向:將p0指向p1;p1指向p2,p1的next指向p0;p2指向下一個節(jié)點

3)循環(huán)執(zhí)行以上步驟,直到p1指向的節(jié)點不為空,最后得到的鏈表為:

4)代碼實現(xiàn):

# encoding=utf-8
import copy
?
?
class Node:
? ? """節(jié)點類,包含值和下一個節(jié)點的指針"""
? ? def __init__(self, value, next=None):
? ? ? ? self.value = value
? ? ? ? self.next = next
?
? ? def __str__(self):
? ? ? ? return "Node value:%s" % self.value
?
?
class LinkedList:
? ? def __init__(self, head=None, tail=None):
? ? ? ? self.head = head
? ? ? ? self.tail = tail
?
? ? def get_all(self):
? ? ? ? """獲取鏈表中所有的節(jié)點"""
? ? ? ? nodes = []
? ? ? ? temp = self.head
? ? ? ? while temp:
? ? ? ? ? ? nodes.append(temp.value)
? ? ? ? ? ? temp = temp.next
? ? ? ? return nodes
?
? ? def add_node(self, value):
? ? ? ? """在列表中添加節(jié)點"""
? ? ? ? node = Node(value)
? ? ? ? # 空鏈表,收尾指針都指向新增加的節(jié)點
? ? ? ? if self.head is None:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? else:
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
?
? ? def reverse_list(self):
? ? ? ? """
? ? ? ? 反轉單向列表
? ? ? ? 思路二:通過3個指針實現(xiàn),p0指向前一個節(jié)點的指針,p1表示當前節(jié)點的指針,p2表示下一個節(jié)點的指針
? ? ? ? :return: LinkedList 對象
? ? ? ? """
? ? ? ? p1 = copy.deepcopy(self.head)
? ? ? ? p2 = p1.next
? ? ? ? # 定義一個新的鏈表對象
? ? ? ? new_list_node = LinkedList()
? ? ? ? while p1:
? ? ? ? ? ? if new_list_node.head is None:
? ? ? ? ? ? ? ? new_list_node.tail = p1
? ? ? ? ? ? # 將p1的next指向新鏈表的頭結點
? ? ? ? ? ? p1.next = new_list_node.head
? ? ? ? ? ? # 將新鏈表的頭結點指向p1
? ? ? ? ? ? new_list_node.head = p1
? ? ? ? ? ? # 將p1指向p2
? ? ? ? ? ? p1 = p2
? ? ? ? ? ? # 判斷p2是否指向了鏈表的末尾
? ? ? ? ? ? if p2:
? ? ? ? ? ? ? ? p2 = p2.next
? ? ? ? return new_list_node
?
?
if __name__ == "__main__":
? ? l = LinkedList()
? ? for i in range(5):
? ? ? ? l.add_node(i)
? ? new_list_node = l.reverse_list()
? ? print(new_list_node.get_all())
? ? print(new_list_node.tail)

4.方式三:

遞歸就是將問題分解為處理過程一致的子問題進行處理,但是一定要要結束條件。鏈表的反轉也可以采用遞歸的方式實現(xiàn),每次傳入的節(jié)點不是最后一個的話,就將下一個節(jié)點作為參數(shù)傳遞進去,遞歸調用;直到傳入的是最后一個節(jié)點時開始逐級返回。

1)將鏈表中每個節(jié)點作為參數(shù),依次傳入到reverse_list函數(shù)中;

2)當傳入的是最后一個節(jié)點時,以此節(jié)點為頭結點創(chuàng)建一個新的鏈表,并將此鏈表返回;

3)上一級的調用者接受到返回的鏈表后,將傳入的節(jié)點作為鏈表的尾結點放到鏈表中;

4)逐級返回,直到回到最開始執(zhí)行reverse_list函數(shù)中,將生成的新鏈表返回即可

5)代碼實現(xiàn):

# encoding=utf-8
import copy
?
?
class Node:
? ? """節(jié)點類,包含值和下一個節(jié)點的指針"""
? ? def __init__(self, value, next=None):
? ? ? ? self.value = value
? ? ? ? self.next = next
?
? ? def __str__(self):
? ? ? ? return "Node value:%s" % self.value
?
?
class LinkedList:
? ? def __init__(self, head=None, tail=None):
? ? ? ? self.head = head
? ? ? ? self.tail = tail
?
? ? def get_all(self):
? ? ? ? """獲取鏈表中所有的節(jié)點"""
? ? ? ? nodes = []
? ? ? ? temp = self.head
? ? ? ? while temp:
? ? ? ? ? ? nodes.append(temp.value)
? ? ? ? ? ? temp = temp.next
? ? ? ? return nodes
?
? ? def add_node(self, value):
? ? ? ? """在列表中添加節(jié)點"""
? ? ? ? node = Node(value)
? ? ? ? # 空鏈表,收尾指針都指向新增加的節(jié)點
? ? ? ? if self.head is None:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? else:
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
?
?
? ? def reverse_list(self, node):
? ? ? ? """
? ? ? ? 反轉單鏈表
? ? ? ? 思路三:用遞歸實現(xiàn)
? ? ? ? :return:LinkedList 對象
? ? ? ? """
? ? ? ? if node.next is None:
? ? ? ? ? ? return LinkedList(node, node)
? ? ? ? temp = copy.deepcopy(node)
? ? ? ? # 斷開當前節(jié)點的連接
? ? ? ? temp.next = None
? ? ? ? # 將當前節(jié)點放到內層遞歸返回的鏈表結尾
? ? ? ? l = self.reverse_list(node.next)
? ? ? ? l.tail.next = temp
? ? ? ? l.tail = temp
? ? ? ? return l
?
?
if __name__ == "__main__":
? ? l = LinkedList()
? ? for i in range(5):
? ? ? ? l.add_node(i)
? ? new_list_node = l.reverse_list1()
? ? print(new_list_node.get_all())
? ? print(new_list_node.tail)

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。

相關文章

  • Python抓取淘寶下拉框關鍵詞的方法

    Python抓取淘寶下拉框關鍵詞的方法

    這篇文章主要介紹了Python抓取淘寶下拉框關鍵詞的方法,涉及Python文件讀寫、正則匹配及字符串操作等相關技巧,需要的朋友可以參考下
    2015-07-07
  • pandas如何實現(xiàn)兩個dataframe相減

    pandas如何實現(xiàn)兩個dataframe相減

    這篇文章主要介紹了pandas如何實現(xiàn)兩個dataframe相減方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-02-02
  • python操作 hbase 數(shù)據(jù)的方法

    python操作 hbase 數(shù)據(jù)的方法

    下面小編就為大家?guī)硪黄猵ython操作 hbase 數(shù)據(jù)的方法。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • Python本地及虛擬解釋器配置過程解析

    Python本地及虛擬解釋器配置過程解析

    這篇文章主要介紹了Python本地及虛擬解釋器配置過程解析,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2020-10-10
  • 關于pip的安裝,更新,卸載模塊以及使用方法(詳解)

    關于pip的安裝,更新,卸載模塊以及使用方法(詳解)

    下面小編就為大家?guī)硪黄P于pip的安裝,更新,卸載模塊以及使用方法(詳解)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-05-05
  • 基于python及pytorch中乘法的使用詳解

    基于python及pytorch中乘法的使用詳解

    今天小編就為大家分享一篇基于python及pytorch中乘法的使用詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • 詳解Python自動化中這八大元素定位

    詳解Python自動化中這八大元素定位

    今天給大家?guī)淼氖顷P于Python的相關知識,文章圍繞著Python自動化中這八大元素定位展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下
    2021-06-06
  • python 獲取當天凌晨零點的時間戳方法

    python 獲取當天凌晨零點的時間戳方法

    今天小編就為大家分享一篇python 獲取當天凌晨零點的時間戳方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-05-05
  • 用python3教你任意Html主內容提取功能

    用python3教你任意Html主內容提取功能

    這篇文章主要介紹了用python3教你任意Html主內容提取功能,主要使用到了requests、lxml、json等模塊,文中逐一對這幾個模塊做了介紹,需要的朋友可以參考下
    2018-11-11
  • OpenCV搞定騰訊滑塊驗證碼的實現(xiàn)代碼

    OpenCV搞定騰訊滑塊驗證碼的實現(xiàn)代碼

    這篇文章主要介紹了OpenCV搞定騰訊滑塊驗證碼,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2019-05-05

最新評論