C++实现链表原地倒置

本文主要介绍了如何使用C++实现链表的原地倒置，包括创建链表、链表倒置和打印链表等操作。 在计算机科学中，链表是一种线性数据结构，其中的元素不是在物理内存中连续存储的，而是通过指针链接。在本例中，我们关注的是单链表，每个节点包含一个整数值（`date`）和指向下一个节点的指针（`next`）。题目要求实现的功能是将给定的链表原地倒置，即不使用额外的数据结构，只改变链表内部的连接关系，使其前后节点位置反转。 首先，定义了链表节点的结构体`list`，包含一个整型数据成员`date`和一个指向下一个节点的指针`next`。同时，使用typedef简化了链表节点指针的表示，定义了一个别名`link`。 接下来，有三个主要的函数： 1. `CoutList(link head)`：这个函数用于打印链表中的所有元素，它遍历链表直到找到末尾（`p->next == NULL`），然后逐个打印节点的`date`值。 2. `link CtreatList()`：此函数用于创建随机长度的链表。它使用`srand`和`rand`函数生成随机数，创建指定长度的链表。链表的最后一个节点的`next`指针设置为`NULL`，表示链表的结束。 3. `link ReverseList(link head)`：这是核心函数，用于原地倒置链表。该函数通过三个指针`p`、`q`和`r`实现链表的反转。初始化时，`p`指向链表头，`q`和`r`都设为`NULL`。在循环中，`q`始终指向`p`的下一个节点，`p->next`被设置为`r`，然后`r`更新为`p`，最后`p`前进到`q`的位置。当`p`到达链表末尾（`p->next == NULL`）时，`r`将指向新的链表头部，原链表头部`head`更新为`r`。 在`main`函数中，首先调用`CtreatList`创建一个随机长度的链表，然后打印原始链表，接着调用`ReverseList`倒置链表，并再次打印倒置后的链表。这样，我们可以看到链表在原地被成功倒置。 总结来说，这个程序实现了链表的原地倒置，这是一种常见的链表操作，对于理解和掌握链表数据结构以及指针操作非常重要。在实际编程中，类似的方法也可以应用于其他数据结构，如双向链表或循环链表的反转。