卡码网语言基础课 | 15. 链表的基础操作 III | 刷题心得

2024-01-08 17:35:46

2024-1-4，卡码网第15题链表的基础操作 III

1. 题目描述

在上两篇博客中，实现了链表的构建(LinkList)、从尾部添加节点（insert）、查询（get）和打印（printlinklist）的功能，这次的题目要求是在实现这些功能的基础上，构建实现链表的给定位置插入节点（insert_at）和删除指定节点（delete）的功能。题目会给出链表初始数据和以上了两个要实现的新功能的相关的数据。那么，选择使用在类中直接定义两个函数 insert_at 和 delete 来实现要比直接在主函数中写相关代码实现更加方便反复调用。

2. 代码实现

接下来，就具体讲一下这两个新增的模块的相关代码应该如何实现。

2.1 指定位置插入（insert_at）

首先，我们需要明白在链表中插入节点，应该有哪几步操作。由于链表的特殊数据结构，所以在插入新节点的前提是找到要插入位置的上一个节点，我们把它定义为 pre_node，新节点定义为new_node。这里，找到 pre_node 需要调用上一篇中创建的链表查询功能（get）。

链表新增查询功能http://t.csdnimg.cn/PL9VJ

pre_node = self.get(n - 1)

接下来，就是插入新节点的具体操作：

让 new_node.next?指向 pre_node.next ，也就是未改动链表的?pre_node 的下一个节点。

new_node.next = pre_node.next

再把 pre_node.next 指向 new_node ,也就是让 pre_node 指向新插入的节点

pre_node.next = new_node

这样就插入了一个新节点了。实际上，就是将链表在指定位置的原有连接断开，把新节点的尾部接上链表的后半部分，把链表的前半部分与新节点的头部相连。形象过程，如下图所示。

在写代码的时候，有几个小细节需要注意：

首先，需要注意插入的节点是否为头节点，如果是头节点，这种情况需要单独列出。
其次，需要判断 n 是否超出了链表原有的范围。在代码中，等同于判断 pre_node 是否为空。
最后，不要忘了增加链表长度，以及将新节点使用 return 返回。

if n == 1:
    new_node.next = self.head_node
    self.head_node = new_node
    self.length += 1 
    return new_node
else:
    pre_node = self.get(n - 1)
    if pre_node is not None:
        new_node.next = pre_node.next
        pre_node.next = new_node
        self.length += 1
        return new_node

2.2 删除指定节点（delete）

删除节点的操作与接入节点的思路类似，只不过是把插入节点的操作顺序反过来。而找到上一个节点的方法也是使用链表查询（get），上一节有讲过，这里就不再赘述了。具体操作步骤如下：

需要判断删除的是否是头节点，删除头节点情况需要单独列出。
找到要删除节点的上一个节点，然后将要删除的节点赋给 delete_node。
然后将 pre_node 下一个节点指向 pre_node 的下下个节点。

这样，就成功将 delete_node 从链表里删除了。这里需要注意到的是：

pre_node 和 pre_node.next 是否为空，如果为空会出现报错，需要加条件语句。
链表的长度不要忘了减，delete_node 需要使用 return 返回出去。
链表是否为空，空链表没法删除节点。

if self.head_node is None:
    return None
if n == 1:
    delete_node = self.head_node
    self.head_node = delete_node.next
    self.length -= 1
    return delete_node
else:
    pre_node = self.get(n - 1)
    if pre_node is not None and pre_node.next is not None:
        delete_node = pre_node.next
        pre_node.next = pre_node.next.next
        self.length -= 1 
        return delete_node

最后，在主函数中，创建实例再调用函数，就可以实现插入节点和删除节点的功能了。代码如下，不再做详细描述了。

#创建一个空链表，读取节点数据和个数
k = int(input())
data = list(map(int, input().split()))
link_list = LinkList()
# 把数据写入链表
for a in data:
    link_list.insert(a)
#插入新节点数据
s = int(input())
for _ in range(s):
    n, x = map(int, input().split())
    new_node = link_list.insert_at(n, x)
    if new_node is not None:
        link_list.printlinklist()
    else:
        print('Insertion position is invalid.')
#删除指定位置节点
l = int(input())
for _ in range(l):
    d = int(input())
    delete_node = link_list.delete(d)
    if delete_node is not None:
        link_list.printlinklist()
    else:
        print('Deletion position is invalid.')

3. 总结

删除节点和在指定位置插入新节点，是构建链表的基础功能之一。这两个模块尤其要注意指定位置是否超出了链表的范围；指定位置是否为头节点；链表是否为空；有没有返回值。再添加了这两个功能后，与前面的功能合并，我们就能够自己用代码实现了一个完整的链表的构建了。

在这三篇文章中，需要熟练掌握构建类和定义类的属性和函数；熟知链表的结构和特点、节点的两个属性；能够对从尾部插入节点、指定位置插入节点和指定位置删除节点有一个清晰的思路；熟练掌握自主构建的类和函数在主函数中的调用；牢记撰写代码时的一些注意细节。

本人所用代码编辑器为 VS Code，刷题网站为卡码网

https://kamacoder.com/https://kamacoder.com/