日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

python反轉單鏈表算法題_python

作者：小小小小人ksh ? 更新時間： 2022-06-28 編程語言

現在算法是大廠面試的必考題，而且越來越難，已經不是簡單的列表，字符串操作了，會涉及到各種數據結結構。單鏈表的反轉也是經常考的一道題，里面故在此記錄一下。

1.鏈表的特點：

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

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

1.先對原鏈表做頭部刪操作，再對新鏈表做頭部插入操作；
2.通過3個指針實現，p0指向前一個節點的指針，p1表示當前節點的指針，p2表示下一個節點的指針
3.用遞歸實現；

2.方式一：

1)創建一個新的空列表；

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

3）依次重復第2）步的操作，直到取出就鏈表中所有的節點。

4）最后形成的新鏈表如下，實現了反轉的功能：

5）代碼實現：

# encoding=utf-8
import copy
?
?
class Node:
? ? """節點類，包含值和下一個節點的指針"""
? ? 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):
? ? ? ? """獲取鏈表中所有的節點"""
? ? ? ? nodes = []
? ? ? ? temp = self.head
? ? ? ? while temp:
? ? ? ? ? ? nodes.append(temp.value)
? ? ? ? ? ? temp = temp.next
? ? ? ? return nodes
?
? ? def add_node(self, value):
? ? ? ? """在列表中添加節點"""
? ? ? ? node = Node(value)
? ? ? ? # 空鏈表,收尾指針都指向新增加的節點
? ? ? ? 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個指針來實現反轉，p0之前前一個節點，p1指向當前操作的節點，p2指向下一個節點。操作過程如下：將p1的next指針之前p0，之后將p0指向p1節點，p1指向p2節點，如果p1不為空，重復以上操作，最后，p0即為新列表的頭節點。

1）開始時p0為空；將p1指向鏈表的頭節點，p1節點的next指針指向p0；p2指向下一個節點：

2）調整3個指針的指向：將p0指向p1；p1指向p2，p1的next指向p0；p2指向下一個節點

3）循環執行以上步驟，直到p1指向的節點不為空，最后得到的鏈表為：

4）代碼實現：

# encoding=utf-8
import copy
?
?
class Node:
? ? """節點類，包含值和下一個節點的指針"""
? ? 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):
? ? ? ? """獲取鏈表中所有的節點"""
? ? ? ? nodes = []
? ? ? ? temp = self.head
? ? ? ? while temp:
? ? ? ? ? ? nodes.append(temp.value)
? ? ? ? ? ? temp = temp.next
? ? ? ? return nodes
?
? ? def add_node(self, value):
? ? ? ? """在列表中添加節點"""
? ? ? ? node = Node(value)
? ? ? ? # 空鏈表,收尾指針都指向新增加的節點
? ? ? ? if self.head is None:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? else:
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
?
? ? def reverse_list(self):
? ? ? ? """
? ? ? ? 反轉單向列表
? ? ? ? 思路二：通過3個指針實現，p0指向前一個節點的指針，p1表示當前節點的指針，p2表示下一個節點的指針
? ? ? ? :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.方式三：

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

1）將鏈表中每個節點作為參數，依次傳入到reverse_list函數中；

2）當傳入的是最后一個節點時，以此節點為頭結點創建一個新的鏈表，并將此鏈表返回；

3）上一級的調用者接受到返回的鏈表后，將傳入的節點作為鏈表的尾結點放到鏈表中；

4）逐級返回，直到回到最開始執行reverse_list函數中，將生成的新鏈表返回即可

5）代碼實現：

# encoding=utf-8
import copy
?
?
class Node:
? ? """節點類，包含值和下一個節點的指針"""
? ? 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):
? ? ? ? """獲取鏈表中所有的節點"""
? ? ? ? nodes = []
? ? ? ? temp = self.head
? ? ? ? while temp:
? ? ? ? ? ? nodes.append(temp.value)
? ? ? ? ? ? temp = temp.next
? ? ? ? return nodes
?
? ? def add_node(self, value):
? ? ? ? """在列表中添加節點"""
? ? ? ? node = Node(value)
? ? ? ? # 空鏈表,收尾指針都指向新增加的節點
? ? ? ? if self.head is None:
? ? ? ? ? ? self.head = node
? ? ? ? ? ? self.tail = node
? ? ? ? else:
? ? ? ? ? ? self.tail.next = node
? ? ? ? ? ? self.tail = node
?
?
? ? def reverse_list(self, node):
? ? ? ? """
? ? ? ? 反轉單鏈表
? ? ? ? 思路三：用遞歸實現
? ? ? ? :return:LinkedList 對象
? ? ? ? """
? ? ? ? if node.next is None:
? ? ? ? ? ? return LinkedList(node, node)
? ? ? ? temp = copy.deepcopy(node)
? ? ? ? # 斷開當前節點的連接
? ? ? ? temp.next = None
? ? ? ? # 將當前節點放到內層遞歸返回的鏈表結尾
? ? ? ? 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)

原文鏈接：https://blog.csdn.net/kongsuhongbaby/article/details/106630731

欄目分類
最近更新