【蓝桥杯冲击国赛计划第1天】单向链表

注意：本文供有一定编程基础的小伙伴阅读，因为这边不会刻意去介绍太多语法层面的内容

1. 链表

1.1 概念

学过 c 语言或者 java 语言的我们应该知道：数组具有连续的储存空间，查找可以通过指定下标进行查找，时间复杂度为 O(1)。但是，数组有个比较麻烦的点就是：移动不便。如图：当第一个元素删除的时候，后续所有元素都需要移动，如果我们从中插入一个元素，插入位置后续的元素也都需要移动。

所以，我们就会思考，有没有什么数据结构可以让插入和删除的操作更加便利呢？链表这时候就显示出他的优势。链表的结点的结构分为两个部分：数据域和指针域。其中，数据域用来存放该结点的数据，指针域用来存放指向下一个结点的指针。

并且，链表的存储空间是不连续的，结点们犹如冰糖葫芦一样，一个个串在一起，这就形成了一个链表。我只要知道一个链表的头结点，那么其他结点我就一定可以得到。

1.2 链表结点的定义

我们通过 python 中的类来定义链表结点

class Node:
    def __init__(self,value,next=None):
        self.value = value
        self.next = next
1
2
3
4

1.3 实例「小王子链表」

我们通过这个实例来了解一下，链表的定义和使用。

题目描述

小王子有一天迷上了排队的游戏，桌子上有标号为 1−10 的 10 个玩具，现在小王子将他们排成一列，可小王子还是太小了，他不确定他到底想把那个玩具摆在哪里，直到最后才能排成一条直线，求玩具的编号。已知他排了 M 次，每次都是选取标号为 X 个放到最前面，求每次排完后玩具的编号序列。

输入描述

第一行是一个整数 M，表示小王子排玩具的次数。

随后 M 行每行包含一个整数 X，表示小王子要把编号为 X 的玩具放在最前面。

输出描述

共 M 行，第 i 行输出小王子第 i 次排完序后玩具的编号序列。

输入输出样例

示例 1

输入

5
3
2
3
4
2
1
2
3
4
5
6

输出

3 1 2 4 5 6 7 8 9 10
2 3 1 4 5 6 7 8 9 10
3 2 1 4 5 6 7 8 9 10
4 3 2 1 5 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10
1
2
3
4
5

运行限制

• 最大运行时间：1s
• 最大运行内存: 128M

1.4 简单分析

每次将想要的玩具提前，其他玩具势必向后移动。这题其实用数组和链表都可以做，但这里由于移动较为频繁且我们需要了解链表这个数据结构，所以我们使用链表来做。

1.5 链表初始化

由于已知玩具的数量，我们先对链表进行初始化。一般为了找到这个链表我们通常都会定义一个无意义的头，如题目中的 Node(0) 作为头结点，这里相当于我做了个标记，这个标记不能动，因为它象征着我的链表。（知道一个链表的头结点 = 知道整条链表），但我们需要进行连接操作的话，必须需要有一个结点来连接，这里我们使用p结点，一开始它等于头结点，然后连接，移动，连接，移动，直至结束。

def createLink(): # 创建链表
    head = Node(0) # 头结点
    p = head
    for i in range(1,11):
        p.next = Node(i) # 连接
        p = p.next # 移动
    return head
1
2
3
4
5
6
7

具体步骤如下：

1.6 链表插入

把想要的玩具放到放到最前面，我们可以直接插入一个新的想要的玩具，之后再删除想要的玩具。比如我想要玩具2，我新建一个玩具2放到最前面，然后再删除之前的玩具2。（其实也不用那么麻烦，但是还是那句话，为了让我们更了解链表的使用）插入的过程虽然较为简单，但这里存在断连接的操作，需要好好讲讲。

欲在头结点和结点1之间插入结点5

• 头结点和结点5先建立联系

  ​

  如果头结点先连接结点5，就会导致头结点和结点1断连接，从而导致无法找到结点1。如果说一定要这样的话，也请先记录结点1。

• 结点5和结点1先建立联系

  

  如果结点5和结点1先进行连接，就不会导致断连接的操作，即可以从头结点到结点1，也可以从头结点到结点5。然后，头结点再和结点5进行连接，这时候头结点和结点1的连接断掉，从而真正将结点5插入进来。

• 插入的代码

  def insertLink(x,head): # 插入x元素
      p = Node(x)
      p.next = head.next # 连接
      head.next = p # 连接
      return head
  1
  2
  3
  4
  5

1.7 链表删除

如图，如果我要删除结点2的话，我直接可以用结点1指向结点3（断了结点1和结点2的连接，但结点2和结点3的连接没有断），但我发现一个问题：当设置一个遍历的变量时，如果我查询到结点2的话，我无法知道结点1，因为是单向链表，从结点2到结点3可以很容易得到，但结点2到结点1就很困难了。所以，我们这里采用两个遍历的变量，一个在前一个在后，在后的变量负责记录我要的值的位置，在前的变量负责记录后的变量记录的前一个位置。

def deleteLink(x,head): # 删除x元素
    p1 = p2 = head # p1:后指针 p2: 前指针
    while p1 != None:
        if p1.value == x:
            p2.next = p1.next
        p2 = p1
        p1 = p1.next
    return head
1
2
3
4
5
6
7
8

1.8 链表打印

最后，最简单的就是打印链表了。只需要一个循环，就可以打印出来。不过，这里要注意的一点是：打印要从头结点的下一个位置开始，因为头结点没有意义。

def showLink(head):
    p = head.next
    while p!= None:
        print(p.value,end=" ")
        p = p.next
    print("")
1
2
3
4
5
6

1.9 主函数

这里一定要先删除后插入，因为先插入再删除，会把插入的那个给删了，这和我们的目的不符。

if __name__ == '__main__':
    head = createLink()
    n = int(input())
    for i in range(n):
        x = int(input())
        deleteLink(x,head)
        insertLink(x,head)
        showLink(head)
1
2
3
4
5
6
7
8

2. 实例的完整代码

可在 我的仓库免费查看，如果无法使用可以及时私信我或在评论区指出，谢谢。

本文主要参考蓝桥杯省赛14天夺奖冲刺营，有兴趣的可以自己在蓝桥杯官网搜索

如有错误，敬请指正，欢迎交流🤝，谢谢♪(･ω･)ﾉ