2024年1月选考 T12 真题解析

通过动画演示链表节点的“头插负数、尾插正数”重排过程，理解按绝对值有序到按值有序的转变。

题目

使用列表 d 模拟链表结构，每个节点包含数据区域和指针区域，h 为头指针。链表中各节点已按数据区域中数值的绝对值由小到大排列。现要修改链接关系，使链表按数值由小到大排列。有如下 Python 程序段（高亮行表示当前执行位置）：

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

若 d = [[1,3],[14,4],[-18,-1],[-11,1],[16,2]]（已按绝对值升序整理），h = 0，运行后链表的节点顺序为 ?

注：为使“按绝对值升序”条件成立，原始输入数据已整理为 d[0]→d[3]→d[1]→d[4]→d[2]→-1。

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

负数节点

正数节点

h 新链头指针

t 正数链尾指针

p 当前遍历节点

q 下一节点（断链保护）

原链表（按绝对值升序，剩余待处理）固定顺序 0 → 3 → 1 → 4 → 2 → -1

新链表（按数值升序，当前已整理）显示 h 到 t 的已整理部分

动画速度：300ms

点击“开始”逐步查看链表重排过程。

初始状态：链表按节点数据绝对值升序排列：1 → 11 → 14 → 16 → 18，对应节点 0 → 3 → 1 → 4 → 2。
目标：改为按实际数值升序排列：-18 → -11 → 1 → 14 → 16。
算法核心：遍历链表时，把负数节点“头插”到新链头部，正数节点“尾插”到正数链尾部。
为什么正确？
- 正数节点原本按绝对值升序，也就是按数值升序，尾插后保持相对顺序：1 → 14 → 16。
- 负数节点原本按绝对值升序（如 -11 → -18），头插后顺序反转（-18 → -11），恰好是按数值升序。
指针作用：h 是新链头，t 是正数链尾，p 是当前遍历节点，q 是 p 的下一个节点（保存后防止断链）。