資訊專欄INFORMATION COLUMN
摘要：單身聯系與雙重聯系在鏈接列表方面，有兩種主要類型。代碼是如何工作的呢編碼鏈接列表可能是行問題或行問題。這將繼續，直到指向，在這種情況下循環停止?，F在您已經掌握了處理鏈表面試問題所需的基本知識
什么是鏈表？
鏈表是一種數據結構，由許多稱為“節點”的迷你數據結構組成。節點鏈接在一起形成一個列表。
整個鏈表，由3個節點鏈接在一起組成。
它的價值。這可以是任何東西：整數，字符，字符串，對象等。
指向序列中下一個節點的指針。
頭節點：頭節點只是鏈表中的第一個節點。從上面的例子可以看出，包含"5"的節點是第一個節點，因此是頭部。
"尾節點：尾節點是序列中的最后一個節點。由于它是最后一個節點，因此它指向null，因為序列中沒有下一個節點。在上面的示例中，包含“3”的節點將是尾節點。
單身聯系與雙重聯系在鏈接列表方面，有兩種主要類型。
那些“多帶帶”聯系的，以及那些“雙重”聯系的。
多帶帶鏈接意味著每個節點僅指向最多1個其他節點，即其前面的節點。這在上面的例子中展示。
雙重鏈接意味著每個節點可以指向其他2個節點，前面的節點和它后面的節點。正如我們從下面的例子中可以看到的那樣，由于頭節點之前沒有節點（即5），因此其中一個指針指向null。
代碼是如何工作的呢？編碼鏈接列表可能是4行問題或400行問題。這取決于你想要如何接近它。
在最簡單的層面上，就像我們討論的那樣，鏈表只是一堆連接的節點。
因此，我們真正需要創建此結構的只是一個節點對象。
class linkedListNode:
def __init__(self, value, nextNode=None):
self.value = value
self.nextNode = nextNode
在這里我們可以看到我們只是創建了一個具有value和nextNode屬性的類。
要創建節點，我們只需傳入一個值。
node1 = linkedListNode("3") # "3"
node2 = linkedListNode("7") # "7"
node3 = linkedListNode("10") # "10"
在這里，我們創建了3個多帶帶的節點。
下一步就是將它們連接在一起。
node1.nextNode = node2 node2.nextNode = node3
上面的第一行使node1指向node2：
“3”→“7”
上面的第二行使node2指向node3：
“7”→” 10"
總之，我們留下了一個鏈接列表，如下所示：
“3”→” 7" →” 10" →null
注意：“10”指向null，因為沒有為node3分配nextNode，并且默認的nextNode為Null。
就像我之前提到的，有很多不同的方法可以做到這一點。這只是最簡單的。
遍歷鏈接列表如果您正在進行編程訪談，并且您會收到鏈接列表問題，那么您將無法獲得所有節點。
所有你得到的是頭節點。
從該頭節點，您必須獲得列表的其余部分。
首先讓我們了解如何從Python中的節點獲取值和nextNode。
假設我們有一個名為"node"的節點。
獲取節點的值：
node.value
獲取節點的nextNode：
node.nextNodeTraversal
我們要做的第一件事就是創建一個名為“currentNode”的變量來跟蹤我們所處的節點。我們首先想要將它分配給我們的頭節點。
currentNode = head
現在我們要做的就是檢查當前節點是否為Null。如果不是，我們將"currentNode"等于"currentNode"的"nextNode"。
currentNode = node1
while currentNode is not None:
currentNode = currentNode.nextNode
假設我們有以下鏈接列表：“3”→“7”→“10”。
我們的頭和第一個"currentNode"是“3”。
當我們這樣做
currentNode = currentNode.nextNode
我們將"currentNode"重新分配給當前節點的鄰居，在這種情況下是“7”。
這將繼續，直到currentNode指向None，在這種情況下循環停止。
這是在Python中遍歷鏈表的基本方法。
鏈接到Github上的代碼。
插入元素將元素插入鏈接列表時，除非另有說明，否則將其插入后面。
我們使用以下示例：
“3”→” 7" →” 10" →空
假設我們要插入一個“4”。
我們只需找到尾節點，在本例中為“10”，并將其nextNode設置為“4”節點。
“3”→” 7" →” 10" →‘4’→null
node4 = linkedListNode("4")
node3.nextNode = node4
假設我們在一個訪談中，我們只有head節點。我們只需遍歷LinkedList即可找到尾部。一旦我們得到尾部，我們只需將其nextNode設置為我們創建的新節點。
def insertNode(head, valuetoInsert):
currentNode = head
while currentNode is not None:
if currentNode.nextNode is None:
currentNode.nextNode = linkedListNode(valuetoInsert)
return head
currentNode = currentNode.nextNode
刪除元素
刪除可能會有點棘手。
我們來看同樣的例子。
“3”→” 7" →” 10" →null
如果我們想要刪除“7”，我們需要做的就是將“3”指向“10”，以便永遠不會引用“7”。
“3”→” 10" →null
要做到這一點，我們必須遍歷列表，同時不僅要跟蹤currentNode，還要跟蹤previousNode。
我們還必須考慮頭節點是我們想要刪除的節點。
在下面的代碼中，我們只刪除要刪除的值的第一個實例。
請注意，有很多方法可以實現這一點，下面的解決方案可能不是您生活中最清晰的代碼。然而，在采訪的熱度中，面試官可能不會期望教科書完美的代碼。
def deleteNode(head, valueToDelete):
currentNode = head
previousNode = None
while currentNode is not None:
if currentNode.value == valueToDelete:
if previousNode is None:
newHead = currentNode.nextNode
currentNode.nextNode = None
return newHead # Deleted the head
previousNode.nextNode = currentNode.nextNode
return head
previousNode = currentNode
currentNode = currentNode.nextNode
return head # Value to delete was not found.
在上面的代碼中，一旦我們找到要刪除的節點，我們將前一節點的“nextNode”設置為已刪除節點的“nextNode”，以將其完全從列表中刪除。
大O時間復雜性分析注意這些是上述節點結構的時間復雜性，最有可能出現在訪談中。在實際情況中，您可以將屬性存儲在LinkedList類中以降低這些復雜性。
"n"=鏈接列表中的元素數量。
插入到鏈接列表的后面 -我們遍歷所有n個元素以找到尾部并插入我們的新節點。O(n)
插入鏈接列表的前面 -?我們只需創建新節點并將其nextNode設置為head。無需遍歷列表。O（1）
遍歷 - ?我們遍歷所有n個元素。O(n)
刪除 -?最糟糕的情況是，我們刪除的節點是最后一個節點，導致我們遍歷整個列表。O(n)
現在您已經掌握了處理鏈表面試問題所需的基本知識!
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/43740.html
摘要：本文我們將討論一個可能出現在面試中的經典問題。問題給定一個字符串作為輸入，刪除任何重復出現的字符，并返回新字符串。為了解決這個問題，我們將使用一個名為的特定數據結構?？臻g復雜性最糟糕的情況是，我們得到一個包含所有唯一字符的字符串。 showImg(https://segmentfault.com/img/remote/1460000018988016); 來源 | 愿碼(ChainD...
摘要：下面代碼會存在什么問題，如何改進一行代碼輸出之間的所有偶數。簡述進程之間如何通信多路復用的作用模型的區別什么是并發和并行解釋什么是異步非阻塞的作用面試題說說你知道的命令如何查看某次提交修改的內容答案掃碼下面的二維碼訂閱即可獲取。 引言 最近在刷面試題,所以需要看大量的 Python 相關的面試題，從大量的題目中總結了很多的知識，同時也對一些題目進行拓展了，但是在看了網上的大部分面試題不...
摘要：使用單引號雙引號和三引號或來表示字符串。不可變的集合函數會以字典類型返回當前位置的全部全局變量。用于將進制整數轉換成進制，以字符串形式表示。返回字符串中最大的字母，或數組中的最大值。的作用就是減少了單行函數的定義。 問題答案由本人整理 1.基礎語法是否熟悉？介紹一下 Python和其他語言最大的區別就是使用行和縮進，而不是大括號（{}）或者分號（;）來控制類、函數或者邏輯判斷。Pyt...
閱讀 3566·2023-04-25 16:35
閱讀 706·2021-10-11 11:09
閱讀 6177·2021-09-22 15:11
閱讀 3360·2019-08-30 14:03
閱讀 2601·2019-08-29 16:54
閱讀 3353·2019-08-29 16:34
閱讀 3060·2019-08-29 12:18
閱讀 2130·2019-08-28 18:31
