第 12 题

s = h       #h 为头指针




print("重排后链表数值顺序:", end=" ")
p = h
while d[p][1] != -1:
    print(d[p][0],end="→")
    p = d[p][1]
print(d[p][0])

题干说明d模拟链表，h是头指针。输出程序用d[p][0]取得当前结点的数据，用p＝d[p][1]转向后继，因此d中每个元素的第0项为数据域，第1项为指针域，保存后继结点在d中的下标；−1表示没有后继结点。s＝h使s也指向原链表的首结点，重排后的输出仍从h所指的首结点开始。

p = -1
cur = s
while cur != -1:
    nxt = d[cur][1]
    d[cur][1] = p
    p = cur
    cur = nxt

代码段①从s所指结点开始处理。每轮先用nxt保存当前结点原后继的下标，再将当前结点的指针域改为p。第一次p＝−1，使原首结点成为末结点；随后p＝cur，让p指向刚处理的结点，cur＝nxt则继续处理原后继。后续结点依次接到已处理部分的前面，由此完成逆置；循环结束时，p保存逆置后首结点的下标。

f = h
while f != -1 and d[f][1] != -1:
    p = s
    s = d[s][1]
    f = d[f][1]
    if f != -1:
        f = d[f][1]
d[p][1] = -1

代码段②中，s每轮沿链表移动一步，f每轮移动两步，p保存s移动前的结点下标。因此，当f到达链表末端时，s到达分割位置，p指向s所指结点的前驱。d[p][1]＝−1切断两者的链接，h、s分别成为前后两段的头指针。原链表有2m个结点时，两段各有m个结点；有2m＋1个结点时，前段有m个，后段有m＋1个。

p1 = h
p2 = q = p
while q != -1:
    q = d[p2][1]
    d[p2][1] = d[p1][1]
    d[p1][1] = p2
    p1 = d[p2][1]
    p2 = q

代码段③令p1、p2分别从h、p所指的结点开始。每轮先用q保存p2所指结点原后继的下标，再将d[p1][1]存入d[p2][1]，使第二段当前结点连接第一段当前结点的原后继；随后将p2存入d[p1][1]，完成插入。最后，p1转向第一段的原后继，p2转向第二段的原后继。该段交替合并两段链表，直到第二段处理完；每次插入时，p1都须指向有效结点。

目标顺序交替取原链表前端和后端的结点，需要先分割链表，再逆置后段，最后交替合并。代码段②完成分割，使s指向后段首结点；代码段①逆置后段，使p保存其新的首结点下标；代码段③以h、p为两个头指针完成合并，因此按②①③排列。

图示6个结点的变化如下：

原代码对奇数结点存在缺陷：后段比前段多一个结点，合并最后一个后段结点前，p1已为−1，程序却仍访问d[p1]。Python中的d[-1]访问列表最后一项，并不表示空结点。例如5个结点L0～L4依次存于d[0]～d[4]时，执行后得到L0→L4→L2→L1→L3，与目标顺序不符。答案B按图示的偶数结点情形成立；题干仅规定“节点数大于2”，不足以保证原程序对全部情况正确。