2024年6月选考 T12 真题解析

通过动画演示链表节点数据按链表顺序整理到数组前端的过程，理解交换数据并维护链接关系的算法思想。

题目

使用列表 d 模拟链表结构（节点数 n>0），每个节点包含数据区域和指针区域，h 为头指针。现要按链表顺序将这 n 个节点中的数据依次存放到 d[0][0]、d[1][0]、…、d[n-1][0] 中，最终保持节点链接关系不变。有如下 Python 程序段（高亮行表示当前执行位置）：

d=[[15,4],[18,0],[12,5],[23,-1],[19,2],[29,3]]
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]
        d[p][1]= d[i][1]
        d[i][1]= p     
        i+=1
    p = tp

已知 d = [[15,4],[18,0],[12,5],[23,-1],[19,2],[29,3]]，头指针 h = 1。初始逻辑顺序为 1 → 0 → 4 → 2 → 5 → 3 → -1，对应数据依次为 18, 15, 19, 12, 29, 23。

节点状态表 d

索引	d[i][0]	d[i][1]

图例

p 遍历指针（原链表顺序）

i 目标位置指针

已在正确位置（p == i）

正在交换/调整（p > i）

本次发生变化的 next 指针

当前变量

p = 1

i = 0

原链表（按链表顺序，参考轨）

固定顺序 1 → 0 → 4 → 2 → 5 → 3 → -1

数组存储状态（目标位置）

物理下标 0 ~ 5，依次存放链表顺序的数据

演示控制

动画速度：500ms

点击“开始”逐步查看链表数据整理过程。

思路解析

初始状态：已知头指针 h = 1，链表逻辑顺序为 1 → 0 → 4 → 2 → 5 → 3 → -1，对应数据 18, 15, 19, 12, 29, 23。
算法目标：不改变原链表的逻辑顺序，只把数据按该顺序依次搬到 d[0][0]、d[1][0]、…、d[n-1][0]，同时保持节点之间的链接关系不变。
双指针作用：
- p 沿着原链表的逻辑顺序遍历，依次访问 1, 0, 4, 2, 5, 3。
- i 表示当前要填入正确数据的目标数组下标，从 0 开始向右移动。
两种情形：
- p == i：当前物理位置正好就是目标位置，数据已经在正确位置，只需把 i 右移。
- p > i：需要把 p 位置的数据交换到 i 位置，并修改相关 next 指针，使链表链接关系保持不变；随后 i 右移。
为什么能保持链接关系？ 交换 d[i][0] 与 d[p][0] 只是把数据搬到正确位置；接着用 d[p][1] = d[i][1]、d[i][1] = p 重新连接指针，确保原链表中“下一个是 p”的节点现在指向 i，而 i 又指向 p 原先的下一个节点。