python反轉(zhuǎn)單鏈表算法題
現(xiàn)在算法是大廠面試的必考題,而且越來(lái)越難,已經(jīng)不是簡(jiǎn)單的列表,字符串操作了,會(huì)涉及到各種數(shù)據(jù)結(jié)結(jié)構(gòu)。單鏈表的反轉(zhuǎn)也是經(jīng)??嫉囊坏李},里面故在此記錄一下。
1.鏈表的特點(diǎn):
順序存儲(chǔ)元素,但是元素在空間上是不連續(xù)的,所以在鏈表每個(gè)元素中除了存儲(chǔ)元素的值,還會(huì)存儲(chǔ)下一個(gè)元素的地址,單鏈表的話(huà)就只有指向下一個(gè)元素的指針,雙向鏈表的話(huà)還會(huì)有指向前一個(gè)元素的指針。正是由于鏈表以上的存儲(chǔ)特點(diǎn),在做插入和刪除操作時(shí)只需要斷開(kāi)指針的連接,不需要移動(dòng)后面的數(shù)據(jù),所以對(duì)鏈表修改的效率會(huì)很高,但是查找的效率會(huì)很低,這也正是鏈表和數(shù)組的區(qū)別。鏈表的存儲(chǔ)示意圖:
完成這道題至少有3種方式:
1.先對(duì)原鏈表做頭部刪操作,再對(duì)新鏈表做頭部插入操作;
2.通過(guò)3個(gè)指針實(shí)現(xiàn),p0指向前一個(gè)節(jié)點(diǎn)的指針,p1表示當(dāng)前節(jié)點(diǎn)的指針,p2表示下一個(gè)節(jié)點(diǎn)的指針
3.用遞歸實(shí)現(xiàn);
2.方式一:
1)創(chuàng)建一個(gè)新的空列表;
2)取出舊鏈表中頭結(jié)點(diǎn)的元素,將其next指針設(shè)置為新鏈表的頭指針,同時(shí)將舊鏈表的頭結(jié)點(diǎn)執(zhí)行下一個(gè)元素
3)依次重復(fù)第2)步的操作,直到取出就鏈表中所有的節(jié)點(diǎn)。
4)最后形成的新鏈表如下,實(shí)現(xiàn)了反轉(zhuǎn)的功能:
5)代碼實(shí)現(xiàn):
# encoding=utf-8 import copy ? ? class Node: ? ? """節(jié)點(diǎn)類(lèi),包含值和下一個(gè)節(jié)點(diǎn)的指針""" ? ? 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é)點(diǎn)""" ? ? ? ? nodes = [] ? ? ? ? temp = self.head ? ? ? ? while temp: ? ? ? ? ? ? nodes.append(temp.value) ? ? ? ? ? ? temp = temp.next ? ? ? ? return nodes ? ? ? def add_node(self, value): ? ? ? ? """在列表中添加節(jié)點(diǎn)""" ? ? ? ? node = Node(value) ? ? ? ? # 空鏈表,收尾指針都指向新增加的節(jié)點(diǎn) ? ? ? ? if self.head is None: ? ? ? ? ? ? self.head = node ? ? ? ? ? ? self.tail = node ? ? ? ? else: ? ? ? ? ? ? self.tail.next = node ? ? ? ? ? ? self.tail = node ? ? ? def reverse_list(self): ? ? ? ? """反轉(zhuǎn)單向列表 ? ? ? ? 思路一:先對(duì)原鏈表做頭刪操作,再對(duì)新鏈表做頭插 ? ? ? ? """ ? ? ? ? # 定義一個(gè)新的鏈表 ? ? ? ? new_list_node = LinkedList() ? ? ? ? temp = copy.deepcopy(self.head) ? ? ? ? while temp: ? ? ? ? ? ? # 1.對(duì)之前的鏈表做頭刪除操作 ? ? ? ? ? ? node = temp ? ? ? ? ? ? temp = temp.next ? ? ? ? ? ? ? # 2.對(duì)新的鏈表做頭插入操作 ? ? ? ? ? ? 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個(gè)指針來(lái)實(shí)現(xiàn)反轉(zhuǎn),p0之前前一個(gè)節(jié)點(diǎn),p1指向當(dāng)前操作的節(jié)點(diǎn),p2指向下一個(gè)節(jié)點(diǎn)。操作過(guò)程如下:將p1的next指針之前p0,之后將p0指向p1節(jié)點(diǎn),p1指向p2節(jié)點(diǎn),如果p1不為空,重復(fù)以上操作,最后,p0即為新列表的頭節(jié)點(diǎn)。
1)開(kāi)始時(shí)p0為空;將p1指向鏈表的頭節(jié)點(diǎn),p1節(jié)點(diǎn)的next指針指向p0;p2指向下一個(gè)節(jié)點(diǎn):
2)調(diào)整3個(gè)指針的指向:將p0指向p1;p1指向p2,p1的next指向p0;p2指向下一個(gè)節(jié)點(diǎn)
3)循環(huán)執(zhí)行以上步驟,直到p1指向的節(jié)點(diǎn)不為空,最后得到的鏈表為:
4)代碼實(shí)現(xiàn):
# encoding=utf-8 import copy ? ? class Node: ? ? """節(jié)點(diǎn)類(lèi),包含值和下一個(gè)節(jié)點(diǎn)的指針""" ? ? 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é)點(diǎn)""" ? ? ? ? nodes = [] ? ? ? ? temp = self.head ? ? ? ? while temp: ? ? ? ? ? ? nodes.append(temp.value) ? ? ? ? ? ? temp = temp.next ? ? ? ? return nodes ? ? ? def add_node(self, value): ? ? ? ? """在列表中添加節(jié)點(diǎn)""" ? ? ? ? node = Node(value) ? ? ? ? # 空鏈表,收尾指針都指向新增加的節(jié)點(diǎn) ? ? ? ? if self.head is None: ? ? ? ? ? ? self.head = node ? ? ? ? ? ? self.tail = node ? ? ? ? else: ? ? ? ? ? ? self.tail.next = node ? ? ? ? ? ? self.tail = node ? ? ? def reverse_list(self): ? ? ? ? """ ? ? ? ? 反轉(zhuǎn)單向列表 ? ? ? ? 思路二:通過(guò)3個(gè)指針實(shí)現(xiàn),p0指向前一個(gè)節(jié)點(diǎn)的指針,p1表示當(dāng)前節(jié)點(diǎn)的指針,p2表示下一個(gè)節(jié)點(diǎn)的指針 ? ? ? ? :return: LinkedList 對(duì)象 ? ? ? ? """ ? ? ? ? p1 = copy.deepcopy(self.head) ? ? ? ? p2 = p1.next ? ? ? ? # 定義一個(gè)新的鏈表對(duì)象 ? ? ? ? new_list_node = LinkedList() ? ? ? ? while p1: ? ? ? ? ? ? if new_list_node.head is None: ? ? ? ? ? ? ? ? new_list_node.tail = p1 ? ? ? ? ? ? # 將p1的next指向新鏈表的頭結(jié)點(diǎn) ? ? ? ? ? ? p1.next = new_list_node.head ? ? ? ? ? ? # 將新鏈表的頭結(jié)點(diǎn)指向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.方式三:
遞歸就是將問(wèn)題分解為處理過(guò)程一致的子問(wèn)題進(jìn)行處理,但是一定要要結(jié)束條件。鏈表的反轉(zhuǎn)也可以采用遞歸的方式實(shí)現(xiàn),每次傳入的節(jié)點(diǎn)不是最后一個(gè)的話(huà),就將下一個(gè)節(jié)點(diǎn)作為參數(shù)傳遞進(jìn)去,遞歸調(diào)用;直到傳入的是最后一個(gè)節(jié)點(diǎn)時(shí)開(kāi)始逐級(jí)返回。
1)將鏈表中每個(gè)節(jié)點(diǎn)作為參數(shù),依次傳入到reverse_list函數(shù)中;
2)當(dāng)傳入的是最后一個(gè)節(jié)點(diǎn)時(shí),以此節(jié)點(diǎn)為頭結(jié)點(diǎn)創(chuàng)建一個(gè)新的鏈表,并將此鏈表返回;
3)上一級(jí)的調(diào)用者接受到返回的鏈表后,將傳入的節(jié)點(diǎn)作為鏈表的尾結(jié)點(diǎn)放到鏈表中;
4)逐級(jí)返回,直到回到最開(kāi)始執(zhí)行reverse_list函數(shù)中,將生成的新鏈表返回即可
5)代碼實(shí)現(xiàn):
# encoding=utf-8 import copy ? ? class Node: ? ? """節(jié)點(diǎn)類(lèi),包含值和下一個(gè)節(jié)點(diǎn)的指針""" ? ? 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é)點(diǎn)""" ? ? ? ? nodes = [] ? ? ? ? temp = self.head ? ? ? ? while temp: ? ? ? ? ? ? nodes.append(temp.value) ? ? ? ? ? ? temp = temp.next ? ? ? ? return nodes ? ? ? def add_node(self, value): ? ? ? ? """在列表中添加節(jié)點(diǎn)""" ? ? ? ? node = Node(value) ? ? ? ? # 空鏈表,收尾指針都指向新增加的節(jié)點(diǎn) ? ? ? ? if self.head is None: ? ? ? ? ? ? self.head = node ? ? ? ? ? ? self.tail = node ? ? ? ? else: ? ? ? ? ? ? self.tail.next = node ? ? ? ? ? ? self.tail = node ? ? ? ? def reverse_list(self, node): ? ? ? ? """ ? ? ? ? 反轉(zhuǎn)單鏈表 ? ? ? ? 思路三:用遞歸實(shí)現(xiàn) ? ? ? ? :return:LinkedList 對(duì)象 ? ? ? ? """ ? ? ? ? if node.next is None: ? ? ? ? ? ? return LinkedList(node, node) ? ? ? ? temp = copy.deepcopy(node) ? ? ? ? # 斷開(kāi)當(dāng)前節(jié)點(diǎn)的連接 ? ? ? ? temp.next = None ? ? ? ? # 將當(dāng)前節(jié)點(diǎn)放到內(nèi)層遞歸返回的鏈表結(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)
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
pandas如何實(shí)現(xiàn)兩個(gè)dataframe相減
這篇文章主要介紹了pandas如何實(shí)現(xiàn)兩個(gè)dataframe相減方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-02-02關(guān)于pip的安裝,更新,卸載模塊以及使用方法(詳解)
下面小編就為大家?guī)?lái)一篇關(guān)于pip的安裝,更新,卸載模塊以及使用方法(詳解)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-05-05python 獲取當(dāng)天凌晨零點(diǎn)的時(shí)間戳方法
今天小編就為大家分享一篇python 獲取當(dāng)天凌晨零點(diǎn)的時(shí)間戳方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-05-05OpenCV搞定騰訊滑塊驗(yàn)證碼的實(shí)現(xiàn)代碼
這篇文章主要介紹了OpenCV搞定騰訊滑塊驗(yàn)證碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05