摘要：单身联系与双重联系在链接列表方面，有两种主要类型。代码是如何工作的呢编码链接列表可能是行问题或行问题。这将继续，直到指向，在这种情况下循环停止。现在您已经掌握了处理链表面试问题所需的基本知识
什么是链表？
链表是一种数据结构，由许多称为“节点”的迷你数据结构组成。节点链接在一起形成一个列表。
整个链表，由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)
现在您已经掌握了处理链表面试问题所需的基本知识!
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/43740.html
摘要：本文我们将讨论一个可能出现在面试中的经典问题。问题给定一个字符串作为输入，删除任何重复出现的字符，并返回新字符串。为了解决这个问题，我们将使用一个名为的特定数据结构。空间复杂性最糟糕的情况是，我们得到一个包含所有唯一字符的字符串。 showImg(https://segmentfault.com/img/remote/1460000018988016); 来源 | 愿码(ChainD...
摘要：下面代码会存在什么问题，如何改进一行代码输出之间的所有偶数。简述进程之间如何通信多路复用的作用模型的区别什么是并发和并行解释什么是异步非阻塞的作用面试题说说你知道的命令如何查看某次提交修改的内容答案扫码下面的二维码订阅即可获取。 引言 最近在刷面试题,所以需要看大量的 Python 相关的面试题，从大量的题目中总结了很多的知识，同时也对一些题目进行拓展了，但是在看了网上的大部分面试题不...
摘要：使用单引号双引号和三引号或来表示字符串。不可变的集合函数会以字典类型返回当前位置的全部全局变量。用于将进制整数转换成进制，以字符串形式表示。返回字符串中最大的字母，或数组中的最大值。的作用就是减少了单行函数的定义。 问题答案由本人整理 1.基础语法是否熟悉？介绍一下 Python和其他语言最大的区别就是使用行和缩进，而不是大括号（{}）或者分号（;）来控制类、函数或者逻辑判断。Pyt...
阅读 3369·2023-04-25 16:35
阅读 511·2021-10-11 11:09
阅读 1773·2021-10-11 10:58
阅读 5480·2021-09-22 15:11
阅读 1733·2021-09-02 15:40
阅读 3243·2019-08-30 14:03
阅读 2468·2019-08-29 16:54
阅读 3216·2019-08-29 16:34
