【真题算法·第二十期】链表

——— ◆ ———

【真题算法·第二十期】链表

📖知识点详解

01什么是链表？

链表（Linked List）是由"节点"串成的线性结构，每个节点包含数据域（存数据）和指针域（存"下一个节点在哪"）。和数组"连续内存、靠下标随机访问"不同，链表靠指针（引用）一步步跳转，所以插入 / 删除节点时只需改指针，不用搬动其他数据。

寻宝游戏——每张纸条写"线索在 B 处"，B 处纸条又指向 C 处，顺着指下去就走完整个链；想在中途塞一张纸条，只要改一下前一张纸条和中途加入纸条的指向即可。

浙江选考考查的链表几乎都用静态链表（数组模拟）：用列表 d，d[i] = [数据, 指针]，h 是头指针（首节点下标），指针用"下一个节点的下标"表示，链尾用 -1 标记。

02核心操作 / 代码模板

Python

# 用列表 d 模拟单链表：d[i] = [数据, 下一节点下标]，h 为头指针
# ① 从头遍历
p = h
while p != -1:
处理(d[p][0])
p = d[p][1] # 顺着指针走到下一个节点

# ② 头插（新节点成为新头）
d[新][1] = h; h = 新

# ③ 尾插（接到链尾）
d[尾][1] = 新; 尾 = 新

# ④ 删除 p 的后继节点
d[p][1] = d[ d[p][1] ][1]

# ⑤ 相邻 p 和 q 节点之间插入新节点
d[新][1] = q; d[p][1] = 新;
p = d[p][1] / p = 新 # 保持p和q相邻

03常见模式 / 变式

模式一：静态链表的基本遍历与指针修改选考标准考法——列表 d 每个元素 [数据, 指针]，h 头指针，所有操作都建立在"沿指针遍历 + 改指针域"之上。

模式二：链表重排（头插 / 尾插分类）按条件把节点分链到"新头"或"新尾"。例如 202401-Q12：节点按数值正负，负的头插、正的尾插，重新串成有序链表。

模式三：按链表顺序搬移数据并保持链接把链表里的数据依次搬到数组对应位置，同时调整指针域，使剩余节点的链接关系不变（202406-Q12）。

模式四：链表遍历计数 / 步数统计用辅助数组记录"每个节点到链尾的步数"，遍历时若后继已算出步数则直接累加，避免重复遍历（202506-Q11）。

模式五：用指针字段把数据链成多条分组链在 data 每个元素末尾追加一个指针字段，按规则把元素链接成多条链表（如"直接入选组"与"补选组"），用 heads[v]/tails[v] 维护各组头尾，再按链顺序合并输出（202501-Q15）。

04链表 vs 数组

05做题技巧：“一画、二分、三跟踪”

一画：摒弃纯脑补，立刻在草稿纸上画出链式结构图（方框表示节点，箭头表示指针域，单独标出头指针 h，p，q...）。

二分：建立强烈的“数据类型意识”：

数据域（Data）：存放实际数值，通常是程序运行数据的迭代、比较的对象。

指针域（Link）：存放的是数组下标（静态链表），它决定节点的连接顺序。节点数据处理完，通常要操作的都是这个区域。

三跟踪：每执行一步指针赋值（如 p = q ，d[0][1] = q），都要在图上标出指针变量的当前指向，避免把“指针变量的值”和“节点的数据”搞混。

🧪真题举例

【2024年01月·第12题】

🔗 来源：[[202401-Q12-链表]]

12.使用列表d模拟链表结构（节点数大于0），每个节点包含数据区域和指针区域，h为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列，如第12题图a所示。现要修改该链表各节点的链接关系，使链表各节点按数据区域中的数值由小到大排列，结果如第12题图b所示。实现该功能的程序段如下，方框中应填入的正确代码为

Python

t = h
p = d[h][1]
while p != -1:
q = d[p][1]
# 方框中填入以下选项代码
p = q
d[t][-1] = -1

Python

if d[p][0] > 0:
d[q][1] = p
d[t][1] = q
else:
d[h][1] = q
h = p

Python

if d[p][0] > 0:
d[t][1] = q
t = q
else:
h = p
d[p][1] = t

Python

if d[p][0] > 0:
d[t][1] = p
t = p
else:
d[p][1] = h
h = p

Python

if d[p][0] > 0:
d[t][1] = q
d[q][1] = p
else:
d[p][1] = h
h = q

📝解析

本题中原始数据已按绝对值由小到大排列，根据数学正负数原理，若其值为负时，一定比前面的所有数都小；若其值为正时，一定比前面所有数都大，因此本题需按顺序依次访问每个元素，若元素值为负，则插入到当前链表的头部（头插），反之插入到链表尾部（尾插）。答案为C。

【2024年06月·第12题】

🔗 来源：[[202406-Q12-链表-数组操作]]

12.使用列表d模拟链表结构（节点数n>0）,如第12题图a所示，每个节点包含数据区域和指针区域,h为头指针。现要按链表顺序将这n个节点中的数据依次存放到 d[0][0]、d[1][0]…d[n-1][0] 中，最终保持节点链接关系不变,结果如第12题图b所示。实现上述功能的Python程序段如下,方框中应填入的正确代码为

Python

p, i = h, 0
while p != -1:
tp = d[p][1]
if p == i:
i += 1
elif p > i:
d[i][0], d[p][0] = d[p][0], d[i][0]
# 方框中填入以下选项代码
i += 1
p = tp
# 调整头指针h及指针区域，保持节点链接关系不变，代码略

Python

d[i][1] = d[p][1]
d[p][1] = i

Python

d[p][1] = d[i][1]
d[i][1] = p

Python

d[i][1] = p
d[p][1] = d[i][1]

Python

d[p][1] = i
d[i][1] = d[p][1]

📝解析

本题考查链表的数据结构理解及指针区域修改。
根据题意，当前节点为 p，从头结点开始遍历。变量 i 从 0 开始递增，当 p 和 i 相等时，链表已按顺序存放到 d[0][0]、d[1][0]…d[n-1][0]，只需继续迭代。当 p > i 时，p 节点的数据应移动到 i 节点位置，故 d[i][0]、d[p][0] = d[p][0]、d[i][0] 交换数据域。接着为保证剩余节点顺序不变，将 p 的指针域改为 i 的指针，即 d[p][1] = d[i][1]。由于 i < p（该节点已处理，将在链表中跳过），遍历后未处理节点次序不变，再将 i 指向 p，即 d[i][1] = p。答案为 C。

【2025年06月·第11题】

🔗 来源：[[202506-Q11-链表-数组操作]]

有如下Python程序段:

Python

tag = [0] * len(data)
p = i = 0
while i < len(data):
if tag[p] == 0 and data[p][1] != -1:
tag[i] += 1
p = data[p][1]
else:
tag[i] += tag[p]
i += 1
p = i

若data为[[11,3],[23,-1],[15,0],[26,1],[63,2]]，运行该程序段后，tag[4]的值为（）
A. 1 B. 2 C. 3 D. 4

📝解析

本题考查数组、列表。
i：数组tag的下标,p：链表data的指针,二维数组 data用于模拟链表，一维数组tag用于记录链表data中每个节点到链表末尾的步数。程序在链表遍历时每次计算tag[i]的值，若当前tag[p]为0时，tag[i]值加1之后，链表继续向后遍历，直至遍历至tag[p]不为0，即p节点已经计算出到链表末尾的步数，并将该步数叠加至i节点的步数上，以此计算出i节点至链表末尾的总步数。
沿着 data数组顺序从i开始往后枚举，若后续节点p没有被访问过(tag[p] == 0)，每找到一个节点就将tag[i]值加一次1。而如果后继节点P已经被访问过(tag[p] != 0)，则将当前节点i的数值tag[i]加上tag[p]，这样就不需要逐个向后遍历。然后处理下一个节点i。因此数组tag 的终值统计了从元素i开始，到链表尾节点经过的节点数量。tag元素值为0相当于链表的尾节点，tag元素值最大的即为链表的头节点。
程序运行过程中，变量i、tag的主要变化如下：

Python

i=0, tag=[2,0,0,0,0]
i=1, tag=[2,0,0,0,0]
i=2, tag=[2,0,3,0,0]
i=3, tag=[2,0,3,1,0]
i=4, tag=[2,0,3,1,4]

综上，选D。

【2023年06月·第15题】

🔗 来源：[[202306-Q15-算法综合]]

15．某工程包含 n 个任务（编号为 0-n-1），每天可以有多个任务同时进行。某些任务之间有依赖关系，如图 a 所示，任务 4 依赖于任务 1，任务 1 依赖于任务 2。即任务 2 完成后才可以开始任务 1，任务 1 完成后才可以开始任务 4，不存在一个任务依赖于多个任务，或多个任务依赖于同一个任务的情况。

现已对该工程的依赖关系进行了梳理，结果如图 b 所示，标记“T”表示依赖关系需保留，标记“F”表示依赖关系需删除。根据每个任务完成所需的天数和梳理后的依赖关系，编写程序，首先删除标记为“F”的依赖关系，然后计算工程最快完成所需的天数，并以工程最快完成所需的天数为期限，计算每个任务最晚必须开始的时间。

请回答下列问题：

(1)若某工程有 6 个任务，任务间依赖关系如图 a 所示，完成任务 0~5 所需天数分别为 2，1，3，5，1，6，则工程最快完成需要______天。

(2)定义如下erase(lst)函数，参数lst 列表的每个元素表示一个依赖关系。函数的功能是删除标记为“F”的依赖关系，返回保留的依赖关系的个数。

Python

def erase(lst):
i=0
j=len(lst)-1
while i<=j:
if lst[i][2]=='T':
i+=1
else: #若不存在依赖关系
if lst[j][2]=='T': #若列表中最后一个元素存在依赖关系
lst[i]=lst[j] #替换掉不存在依赖关系的元素
i+=1 #i指代个数当前元素被替换成存在依赖关系的节点，可以去判断下一个元素的依赖关系
j-=1 #不管j指向的元素是否存在依赖关系，当其元素被判断并被删除或忽视时，j都要-1
return i #i为当前存在依赖关系节点的个数

若 lst 列表依次存储图 b 所示的依赖关系，如lst[0]为[0，5，‘T’]，调用 erase(lst)的数，则语句"lst[i]=lst[j]”的执行次数为_____。

（3）实现上述功能的部分Python程序如下，请在划线处填入合适的代码

Python

def proc(n, lst, task):
pr = [0] * n
w = [0] * n
m = erase(lst)
for i in ___①____:
task[lst[i][1]][1] = lst[i][0]
pr[lst[i][0]] = 1
c = []
days = 0
for i in range(n):
if pr[i] == 0:
k = i
s = 0
while k != -1:
c.append(k)
s += task[k][0]
___②____
if s > days:
days = s
for i in range(n - 1, -1, -1):
k = c[i]
if task[k][1] == -1:
w[k] = days - task[k][0] + 1
else:
___③____
#输出 days,以及保存在 w 中的每个任务最晚必须开始的时间,代码略
'''
工程包含的任务数存入变量 n
任务间的依赖关系存入 lst 列表
lst[i]包含 3 项，任务 lst[i][0]依赖于任务 lst[i][1]，lst[i][2]存放保留/删除标记任务数据存入
task 列表
task[i]包含 2 项，task[i][0]为完成任务 i 所需天数，task[i][1]的初值为-1
代码略
'''
proc(n, lst, task)

📝解析

（1）8
（2）1
（3）① range(m) ② k=task[k][1]③ w[k]=w[task[k][1]]-task[k][0]

详细解析见公众号：

【真题解析】2023年06月浙江技术选考信息技术第15题超详细解析

【真题图解】2023年06月浙江技术选考信息技术第15题图示解析

【2025年01月·第15题】

🔗 来源：[[202501-Q15-算法综合]]

15.某市举行体育赛事活动,n所学校的选手已完成预赛,现计划根据预赛的成绩挑选s名选手参加市决赛。成绩位列所在学校前w名次的选手直接入选,剩余名额按成绩由高到低依次挑选,成绩相同的选手一并入选,选中的选手数一旦达到或超过s名,挑选结束。

现给定所有选手预赛的成绩数据表,每位选手的数据包含学校编号(0~n-1)、选手编号、成绩,成绩数据表已按成绩由高到低排列。编写程序,计算各选手的校内名次,再按上述规则挑选决赛选手,按成绩数据表中的顺序输出选手编号,同时提供查询功能。选手校内名次的计算方法是：若选手所在学校有m人成绩高于该选手,则该选手的名次为m+1。

在第15题图所示的样例中,n、s、w分别为3、8、2,根据图中前3行数据计算出了每位选手的校内名次,进而选出实际入选的9名选手。

第15题图

请回答下列问题：

(1)对于第15题图所示前4行数据,若s、w分别为5和1,则0号学校入选人数是____▲___。

(2)定义如下search(data,sid,score)函数,data列表每个元素的前5个数据项依次为学校编号、选手编号、成绩、校内名次、是否入选,列表已按成绩由高到低排列。函数功能是查找选手编号为sid、成绩为score的元素,返回其下标,若未找到则返回-1。

Python

def search(data, sid, score):
left , right = 0 , len(data) - 1
f = -1
while left <= right:
mid = (left + right) // 2
if score == data[mid][2]:
f = mid
left = mid + 1
elif score < data[mid][2]:
left = mid + 1
else:
right = mid - 1
if f == -1:
return -1
for i in range(f, len(data)): #“加框处”在range括号内
if data[i][2] != score:
return -1
elif data[i][1] == sid:
return i
return -1

①调用search函数,若data列表长度为12,data[0][2],data[1][2],…,data[11][2]的值依次为：198,185,183,182,182,177,177,176,175,163,161,161,score值为177,则while语句中循环体的执行次数是 ▲ 。

②程序中加框处代码有错,请改正。

(3)实现根据选手成绩(成绩不超过200)计算校内名次,以及挑选决赛选手功能的Python程序如下,请在划线处填入合适的代码。

Python

def proc(data, n, s, w):
#创建r列表,共n个元素,每个元素的值均为[0,0,201], 代码略
heads = [-1, -1]
tails = [-1, -1]
cnt = 0
for i in range(len(data)):
______①_____
r[k][1] += 1
if data[i][2] < r[k][2]:
r[k][2] = data[i][2]
______②______
data[i][3] = r[k][0]
data[i].append(-1) #为data[i]添加一个元素-1
v = 1
if data[i][3] <= w:
data[i][4] = True
cnt += 1
v = 0
if heads[v] == -1:
heads[v] = i
else:
data[tails[v]][5] = i
tails[v] = i
p , q = heas[0] , heads[1]
res = [] #res列表用于存放入选决赛的选手编号,顺序与data列表保持一致
while cnt < s and q != -1:
tmp = data[q][2]
while q != -1 and data[q][2] == tmp:
______③______:
res.append(data[p][1])
p = data[p][5]
res.append(data[q][1])
data[q][4] = True
cnt += 1
q = data[q][5]
while p != -1:
res.append(data[p][1])
p = data[p][5]
return res
'''读取n、s、w;读取选手成绩数据表存入data列表,每个元素包含学校编号、选手编号、成绩、校内名次(初值为0)、是否入选(初值为False)5个数据项,代码略'''
res=proc(data,n,s,w)
#输出res列表中的入选选手编号,代码略
#读取待查询的选手编号与成绩,调用search函数,根据返回值输出查询结果,代码略