【蓝桥杯冲击国赛计划第2天】双向链表、循环链表

1. 双向链表

1.1 概念

单向链表我们只能从一个方向找我想要的结点，而双向链表可以双向找我想要的结点。就比如在只用一个变量遍历链表中的元素时，我们发现到了要删的元素的时候，无法得到他的上一个元素，而双向链表就可以在使用一个变量遍历链表时得到前面的元素。

事实上，单向链表也可以用一个变量遍历元素做到删减的功能，等下在循环链表有应用。

双向链表由数据域，左指针域和右指针域组成。

相互连接关系为：

前一个结点的右指针指向后一个结点，后一个结点的左指针指向前一个结点。

我们暂时先将结点简化为：

1.2 结点的定义

根据 python 类的定义双向链表的结点：

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

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 链表初始化

先右连接下一个，再左连接上一个（左连接这里用的是需要用建立好的连接先从右连接到下一个结点，然后再用左连接连接到上一个结点）

def createLink(): # 创建链表
    head = Node(0)
    p = head
    for i in range(1,11):
        p.right = Node(i) # 右连接下一个
        p.right.left = p # 左连接上一个
        p = p.right # 移动
    return head
1
2
3
4
5
6
7
8

1.5 链表插入

欲在头结点和结点1之间插入结点5，注意以下只是其中一种插入方法

• 结点5和结点1的连接
  结点5和结点1先建立右连接，然后结点1与结点5建立左连接，与此同时，结点1到头结点的左连接中断

• 头结点和结点5的连接
  头结点建立与结点5的右连接时，头结点到结点1的右连接中断，至此头结点与结点1没有任何连接，最后，结点5左连接头结点。

• 插入的代码

  def insertLink(x,head): # 插入x元素
      p = Node(x)
      p.right = head.right # 插入的结点建立右连接
      p.right.left = p # 再建立其左连接
      head.right = p # 头和插入结点建立右连接
      p.left = head # 再建立其左连接
      return head
  1
  2
  3
  4
  5
  6
  7

1.6 链表删除

注意以下只是其中一种删除方法，代码采用的是先建立左连接，再建立右连接的方法

• 先建立右连接

  若结点 i 与 i+2 建立右连接，则结点 i 与待删除结点的右连接中断

• 再建立左连接

  若结点 i+2 与 i 建立左连接，则结点 i+2 与待删除结点的左连接中断

• 删除的代码

  def deleteLink(x,head): # 删除x元素
      p = head
      while p != None:
          if p.value == x:
              p.right.left = p.left # 建立左连接
              p.left.right = p.right # 建立右连接
          p = p.right
      return head
  1
  2
  3
  4
  5
  6
  7
  8

1.7 链表打印

和单向链表一样，不过使用 right 指向下一个

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

1.8 主函数

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

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. 循环链表

2.1 概念

我们将单向链表的头结点和尾结点相连，就组成了新的一种链表，循环链表。（我们这里一般较少用双向链表去建立循环链表，因为他的删除和加入和结点结构都比单向链表复杂）。

循环链表的结构：

2.2 结点的定义

由于由单向链表组成，所以结点的定义并无区别。

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

2.3 实例「约瑟夫环」

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

题目描述

设有 n 个人围坐在圆桌周围，现从某个位置 k 上的人开始报数，报数到 m 的人就站出来。下一个人，即原来的第 m+1 个位置上的人，又从 1 开始报数，再报数到 m 的人站出来。依次重复下去，直到全部的人都站出来为止。试设计一个程序求出这 n 个人的出列顺序。

要求一：采用循环链表解决。

要求二：可以使用模拟法，模拟循环链表。

要求三：可以不使用循环链表类的定义使用方式。

输入描述

输入只有一行且为用空格隔开的三个正整数 n,k,m，其含义如上所述。

输出描述

共 n 行，表示这 n 个人的出列顺序。

输入输出样例

示例 1

输入

3 5 8
1

输出

3
2
1
1
2
3

运行限制

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

2.4 简单分析

如果使用数组也能做，要不就是删除数组中的元素（需要进行多次移动），要不就是设置一个标记出列的为 0 ，未出列的为 1，但这可能需要频繁判断数组元素是否出列。所以这里还是采用循环链表来做。

2.5 链表初始化

和单向链表一致，只是尾结点连接的不再是 none，而是 head，注意这里：头结点并不再是无意义的数值，而是有数据元素的结点，也就是没有头结点这个说法了，而是首元结点： 单链表中第一个有数据元素的结点。

在初始化时我们也要注意 <1 个结点肯定构不成链表，而 1 个结点没必要用循环链表，再怎么循环都是它自己，所以我们先判断再连接。

def createLink(n):
    # 先判断
    if n <= 0:
        return False
    elif n == 1:
        return Node(1)
    else:
        head = Node(1)
        p = head
        for i in range(2,n+1):
            p.next = Node(i)
            p = p.next
        p.next = head # 首尾相接
    return head
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.6 链表模拟过程（主函数）

2.6.1 输入数据

我们可以通过 map 函数输入 n,k,m，然后创建循环列表，并定义遍历变量 p

n,k,m = map(int,input().split())
head = createLink(n)
p = head
1
2
3

2.6.2 循环遍历 p 到第一次 k 的位置

从结点 1 到结点 k 需要移动 k-1 步

## 先到k的位置
for i in range(k-1):
    p = p.next
1
2
3

2.6.3 模拟

我们移动后的步骤应该就是删除了，由于我们使用的是一个变量的遍历，他一定在待删除结点的上一个结点，所以约舍夫环出队的元素应该在该变量的下一个结点里。如果我们只剩一个结点，即它根据定义应该是待删除结点的上一个结点，当打印出队元素的时候会是空，所以应该在删除之前加上一个循环判定，如果结点不是链表中最后的结点，执行删除和打印操作。

while p.next != p: # p 不是最后的结点
1

我们从刚才的模拟过程应该知道：p 是待删除结点的上一个结点，所以应该报数到 m-1 ,而报数 m-1 需要移动 m-2次（如报数 3，1 到 3 只需移动 2 步）

for i in range(m-2): # 找到该删除指针的上一个指针
    p = p.next
1
2

这时候我们指向要删除的上一个结点，所以我们先打印出来

print(p.next.value) 
1

再进行删除操作：

p.next = p.next.next # 连接
p = p.next # 重新从1开始报数
1
2

由于之前我们的循环判断的是：p 不是最后的结点，所以跳出循环还有一个结点，我们也要打印出来。

print(p.value)
1

3. 完整代码

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

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

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