给定一个带头结点的单链表，编写算法将其原地逆置。所谓“原地”是指空间复杂度为O(1)。有两种方法，头插法和冒泡法。这两种方法的时间复杂度均为O(n)。
我们知道，用头插法建立链表，得到的链表中元素的顺序和输入的顺序相反，所以利用这一特点，可以将链表逆置。
给定一个带头结点的单链表L，如下图所示。
首先用指针p存储链表第一个结点，然后将头结点从链表中剥离下来，如下图所示，此时链表L只有一个头结点。
另设一指针r保存p的后继，将p指向的结点N1用尾插法插入到链表L中，
此时p指向N2，保存p的后继N3，再将N2尾插到链表L中，
以此类推，直至保存后继的指针r为空，退出循环。
我把这种方法称为“冒泡法”，是因为算法流程和冒泡排序类似，只不过在冒泡排序中是相邻的元素出现逆序才交换，而链表逆置则要求每对结点之间都要交换顺序。
冒泡法和头插法不同，头插法只有一个工作指针p指向一个操作对象——被摘下来的结点，以及存储其后继的指针r。而冒泡法有两个工作指针，即一对工作指针，以及存储其后继的指针r，共计3个指针。考虑如下一般情况，
指针pre和p分别指向两个结点，将其看作一对结点，它们是每次循环操作的对象。循环中，让N2的后继指向N1，即完成了(N1,N2)的逆置。之后三个指针进一，pre=p，p=r，r=r->next，重复上述逆置操作，链表变成了下图。
显而易见，如果指针，则循环还要继续下去，若，循环结束，链表逆置完成，而指针p指向逆置后的一个元素。
上述步骤发生的前提是链表中除了头结点以外，至少有两个结点，而为了将判断是否继续循环和是否进入循环结合起来，应将指针r初始置为指向第一个结点的后继，p指向第一个结点，即，指针pre无强制要求。
注意初始p指向的结点在完成逆置之后将成为最后一个结点，所以应该在逆置之前将p的后继置为空，否则逆置之后p的后继会指向倒数第二个结点，而倒数第二个结点的后继指向倒数第一个结点，即逆置前的p，两个结点之间形成环。
- data-structure/linklist.c at master · tianshihao/data-structure (github.com)
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/jjc/26437.html