2019 年 408 数据结构 · 第 41 题

Question

2019 年 408 真题

选中文字高亮 · 下划线

设线性表 $L = (a_{1}, a_{2}, a_{3}, \dots, a_{n - 1}, a_{n - 1}, a_{n})$ 采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node {
    int data;
    struct node *next;
} NODE;

请设计一个空间复杂度为 $O (1)$ 且时间上尽可能高效的算法，重新排列 $L$ 中的各结点，得到线性表 $L^{'} = (a_{1}, a_{n}, a_{2}, a_{n - 1}, a_{3}, a_{n - 2}, \dots)$ 。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度。