Python面试问题指南:如何编码链表

栏目: 数据库 · 发布时间: 5年前

内容简介:链表是一种数据结构,由许多称为“节点”的迷你数据结构组成。节点链接在一起形成一个列表。整个链表,由3个节点链接在一起组成。

Python面试问题指南:如何编码链表

什么是链表?

链表是一种数据结构,由许多称为“节点”的迷你数据结构组成。节点链接在一起形成一个列表。

整个链表,由3个节点链接在一起组成。

每个节点包含2个属性

  1. 它的价值。这可以是任何东西:整数,字符,字符串,对象等。
  2. 指向序列中下一个节点的指针。

一些定义

头节点:头节点只是链表中的第一个节点。从上面的例子可以看出,包含'5'的节点是第一个节点,因此是头部。

'尾节点:尾节点是序列中的最后一个节点。由于它是最后一个节点,因此它指向null,因为序列中没有下一个节点。在上面的示例中,包含“3”的节点将是尾节点。

单身联系与双重联系

在链接列表方面,有两种主要类型。

那些“单独”联系的,以及那些“双重”联系的。

单独链接意味着每个节点仅指向最多1个其他节点,即其前面的节点。这在上面的例子中展示。

Python面试问题指南:如何编码链表

双重链接意味着每个节点可以指向其他2个节点,前面的节点和它 后面的节点。 正如我们从下面的例子中可以看到的那样,由于头节点之前没有节点(即5),因此其中一个指针指向null。

Python面试问题指南:如何编码链表

代码是如何工作的呢?

编码链接列表可能是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面试问题指南:如何编码链表

从该头节点,您必须获得列表的其余部分。

首先让我们了解如何从 Python 中的节点获取值和nextNode。

假设我们有一个名为'node'的节点。

获取节点的值:

node.value

获取节点的nextNode:

node.nextNode

Traversal

我们要做的第一件事就是创建一个名为“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)

现在您已经掌握了处理链表面试问题所需的基本知识!


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

浅薄

浅薄

[美] 尼古拉斯·卡尔 / 刘纯毅 / 中信出版社 / 2010-12 / 42.00元

《浅薄:互联网如何毒化了我们的大脑》在我们跟计算机越来越密不可分的过程中,我们越来越多的人生体验通过电脑屏幕上闪烁摇曳、虚无缥缈的符号完成,最大的危险就是我们即将开始丧失我们的人性,牺牲人之所以区别于机器的本质属性。——尼古拉斯•卡尔“谷歌在把我们变傻吗?”当尼古拉斯•卡尔在发表于《大西洋月刊》上赫赫有名的那篇封面文章中提出这个问题的时候,他就开启了人们热切渴望的期盼源泉,让人急于弄清楚互联网是在......一起来看看 《浅薄》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试