206. 反转链表

链接：https://leetcode.cn/problems/reverse-linked-list/

$$\varnothing \leftarrow \begin{array}{cc}a& b\end{array}\leftrightarrows \begin{array}{cc}c& d\end{array}\to \varnothing$$

这里我们主要介绍的是链表中最复杂的结构：循环双向链表 (Circular Doubly Linked List)

数据结构：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int DataType;
typedef struct CDList {
    DataType data;
    struct CDList *prev; // 指向上一结点
    struct CDList *next; // 指向下一结点
} Node;

这里的单链表是无头非循环的，与 数据结构 - 单链表 中介绍的一致，并使用到头文件：

链表的表示

顺序表的问题及思考

问题：

1. 中间、头部的插入删除，时间复杂度为 $O(N)$；
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈 2 倍的增长，势必会有一定的空间浪费。例如当前容量为 100，满了以后增容到
   200，我们再继续插入了 5 个数据，后面没有数据插入了，那么就浪费了 95 个数据空间。