题20

题20

题目

【2019 统考真题】设线性表 采用带头结点的单链表保存，链表中的结点定义如下：

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

请设计一个空间复杂度为 且时间上尽可能高效的算法，重新排列 中的各结点，得到线性表 。要求：
⑴ 给出算法的基本设计思想。
⑵ 根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
⑶ 说明你所设计算法的时间复杂度。

分析

题8

解

1. 算法的基本设计思想

先观察 和 ,发现 是由 摘取第一个元素, 再摘取倒数第一个元素……依次合并而成的。为了方便链表后半段取元素, 需要先将 后半段原地逆置
题目要求空间复杂度为 ,不能借助栈
否则每取最后一个结点都需要遍历一次链表。
①先找出链表 的中间结点,为此设置两个指针 p 和 q ,指针 p 每次走一步,指针 q 每次走两步,当指针 q 到达链尾时,指针 p 正好在链表的中间结点;
②然后将 的后半段结点原地逆置。
③从单链表前后两段中依次各取一个结点, 按要求重排。

// 算法实现
void change_list(NODE* h) {
    NODE* p, *q, *r, *s;
    p = q = h;
 
    while (q->next != NULL) { // 寻找中间结点
        p = p->next; // p 走一步
        q = q->next;
        if (q->next != NULL) q = q->next; // q 走两步
    }
 
    q = p->next; // p 所指结点为中间结点, q 为后半段链表的首结点
    p->next = NULL;
 
    while (q != NULL) { // 将链表后半段逆置
        r = q->next;
        q->next = p->next;
        p->next = q;
        q = r;
    }
 
    s = h->next; // s 指向前半段的第一个数据结点,即插入点
    q = p->next; // q 指向后半段的第一个数据结点
    p->next = NULL;
 
    while (q != NULL) { // 将链表后半段的结点插入到指定位置
        r = q->next; // r 指向后半段的下一个结点
        q->next = s->next; // 将 q 所指结点插入到 s 所指结点之后
        s->next = q;
        s = q->next; // s 指向前半段的下一个插入点
        q = r;
    }
}

3. 第一步找中间结点的时间复杂度为 O(n) ,第二步逆置的时间复杂度为 O(n) ,第三步合并链表的时间复杂度为 O(n) ,所以该算法的时间复杂度为 O(n) 。