卡码网语言基础课 | 15. 链表的基础操作③_Python

1、问题描述

题目描述：
请编写一个程序，实现以下链表操作：构建一个单向链表，链表中包含一组整数数据。
（1）实现在链表的第 n 个位置插入一个元素，输出整个链表的所有元素。
（2）实现删除链表的第 m 个位置的元素，输出整个链表的所有元素。
要求：
（1）使用自定义的链表数据结构。
（2）提供一个 linkedlist 类来管理链表，包含构建链表、插入元素、删除元素和输出链表元素的方法。
（3）在 main 函数中，创建一个包含一组整数数据的链表，然后根据输入的 n 和 m，调用链表的方法插入和删除元素，并输出整个链表的所有元素。

输入描述：每次输出只有一组测试数据。每组的第一行包含一个整数 k，表示需要构建的链表的长度。第二行包含 k 个整数，表示链表中的元素。第三行包含一个整数 s，表示后续会有 s 行输入，每行两个整数，第一个整数为 n，第二个整数为 x ，代表在链表的第 n 个位置插入 x。
s 行输入…
在 s 行输入后，后续会输入一个整数 l，表示后续会有 l 行输入，每行一个整数 m，代表删除链表中的第 m 个元素。
l 行输入…

输出描述：包含多组输出。每组第一行输出构建的链表，链表元素中用空格隔开，最后一个元素后没有空格。然后是 s 行输出，每次插入一个元素之后都将链表输出一次，元素之间用空格隔开，最后一个元素后没有空格；如果插入位置不合法，则输出“insertion position is invalid.”。
然后是 l 行输出，每次删除一个元素之后都将链表输出一次，元素之间用空格隔开，最后一个元素后没有空格；如果删除元素后链表的长度为0，则不打印链表。如果删除位置不合法，则输出“deletion position is invalid.”。如果链表已经为空，执行删除操作时不需要打印任何数据。

输入示例：

输出示例：

1 2 3 3 4 5
1 2 4 3 3 4 5
insertion position is invalid.
2 4 3 3 4 5
deletion position is invalid.

2、链表的插入与删除

① 链表的插入

在这里插入图片描述我们可以假设这样一个场景：在传递情报过程中，a 的下线是 b , 也就是 a.next = b，现在我们要引入一个 c 充当 a 和 b 之间的中间人，新的关系是 a 的下线是 c , c 的下线是 b，我们可以直接将 c 的 next 指向 b，但是 b 无法直接表示，之前是用 a.next 来表示 b 的，即 c.next = a.next，然后再将 a 的 next 指向 c , 即 a.next = c，这样就将新的关系构建完成了。

在链表中，具体插入的过程如下：
ⅰ. 如果要在头节点处插入新的节点 (新的节点成为头节点)：
（1）新节点的 next 指针指向原来的头节点： new_node.next = head_node
（2）新节点成为新的头节点 new_node = head_node
（3）链表长度 + 1
ⅱ. 如果要在非头节点处插入新的节点
（1）找到要插入的位置的前一个节点，将之命名为pre_node
（2）将新节点的 next 指针指向 pre_node 的 next 指针，即 new_node.next = pre_node.next
（3）将 pre_node 的 next 指针指向新节点，即 pre_node.next = new_node
（4）链表长度 + 1
这样就完成了链表节点的插入过程。转换成代码如下：

# 在第 n 个位置插入元素
def insert_at(self, n, data):
    new_node = node(data)
    if n == 1: # 在头节点处插入新节点
        new_node.next = self.head_node # 新节点的 next 指针指向原来的头节点
        self.head_node = new_node # 新节点成为新的头节点
        self.length += 1 # 链表长度 +1
        return new_node
    else: # 在非头节点处插入新节点
        pre_node = self.get(n-1) # 使用 get 方法获取要插入位置的前一个节点，命名 pre_node
        if pre_node is not none: 
            new_node.next = pre_node.next # 将新节点的 next 指针指向 pre_node 的 next 指针
            pre_node.next = new_node # 将 pre_node 的 next 指针指向新节点
            self.length += 1 # 链表长度 +1
            return new_node
    return none

② 链表的删除

删除链表的过程同样要区分是否有头节点

ⅰ. 如果链表不存在头节点：表示链表为空，返回none
ⅱ. 如果链表存在头节点 (链表不为空)，要删除头节点
（1）新的头节点指向当前头节点的next节点
（2）链表长度 -1
在这里插入图片描述 ⅲ. 如果链表存在头节点，要删除非头节点
（1）找到删除节点的前一个节点pre_node
（2）并将其next 指针设置为指向下下个节点，从而跳过了下一个节点，实现了节点的删除操作。
（3）链表长度 -1
这样就完成了链表节点的删除过程。转换成代码如下：

def delet(self, n):
    if self.head_node is none: # 判断头节点是否还存在, 即链表是否为空链表
        return none
    if n == 1: # 如果要删除的是头节点
        deleted_node = self.head_node
        self.head_node = self.head_node.next # 当前头节点的下一个节点成为新的头节点
        self.length -= 1
        return deleted_node
    else: # 如果要删除的不是头节点
        pre_node = self.get(n-1) # 找到要删除的节点的前一个节点
        if pre_node is not none and pre_node.next is not none:
            deleted_node = pre_node.next
            pre_node.next = pre_node.next.next # 跳过要删除的节点
            self.length -= 1
            return deleted_node # 返回删除的节点
    return none

3、代码

# 定义链表节点
class node:
    def __init__(self, data):
        self.data = data
        self.next = none
# 定义链表
class linkedlist:
    def __init__(self):
        self.head_node = none
        self.length = 0
    # 尾部插入方法
    def insert(self, data):
        new_node = node(data)
        self.length += 1
        if self.head_node is none:
            self.head_node = new_node
            return self.head_node
        else:
            current_node = self.head_node
            while current_node.next is not none:
                current_node = current_node.next
            current_node.next = new_node
            return new_node
    # 获取第 n 个节点方法
    def get(self, n):
        if n < 1 or n > self.length:
            return none
        i = 1
        current_node = self.head_node
        while current_node is not none:
            if i == n:
                return current_node
            i += 1
            current_node = current_node.next
        return none
    # 插入节点方法
    def insert_at(self, n, data):
        new_node = node(data)
        if n == 1:
            new_node.next = self.head_node
            self.heand_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
            return none
    # 删除节点方法
    def delet(self, n):
        if self.head_node is none:
            return none
        if n == 1:
            deleted_node = self.head_node
            self.head_node = self.head_node.next
            self.length -= 1
            return deleted_node
        else:
            pre_node = self.get(n-1)
            if pre_node is not none and pre_node.next is not none:
                deleted_node = pre_node.next
                pre_node.next = pre_node.next.next
                self.length -= 1
                return deleted_node
        return none
    # 打印链表节点方法
    def print_link_list(self):
        current_node = self.head_node
        while current_node is not none:
            if current_node.next is not none:
                print(current_node.data, end=' ')
            else:
                print(current_node.data)
            current_node = current_node.next

k = int(input())
# 新建链表
link_list = linkedlist()
elements = list(map(int, input().split()))
# 将元素插入到链表中
for element in elements:
    link_list.insert(element)

s = int(input())
for _ in range(s):
    n, x = map(int, input().split())
    # 在索引 n 处插入链表节点
    node = link_list.insert_at(n, x)
    if node is not none:
        link_list.print_link_list()
    else:
        print("insertion position is invalid.")

l = int(input())
for _ in range(l):
    m = int(input())
    # 在索引 m 处删除链表节点
    deleted_node = link_list.delet(m)
    if deleted_node is not none:
        link_list.print_link_list()
    else:
        print("insertion position is invalid.")