单向链表反转java实现头插法（单向链表逆序 java）

科技前沿 • 2025-05-14 08:42 • 阅读 49

大家好，我是讯享网，很高兴认识大家。

给定一个带头结点的单链表，编写算法将其原地逆置。所谓“原地”是指空间复杂度为O(1)。有两种方法，头插法和冒泡法。这两种方法的时间复杂度均为O(n)。

我们知道，用头插法建立链表，得到的链表中元素的顺序和输入的顺序相反，所以利用这一特点，可以将链表逆置。

给定一个带头结点的单链表L，如下图所示。

首先用指针p存储链表第一个结点，然后将头结点从链表中剥离下来，如下图所示，此时链表L只有一个头结点。

java实现链表的逆置算法链表逆置的两种方法_结点_02

另设一指针r保存p的后继，将p指向的结点N1用尾插法插入到链表L中，

java实现链表的逆置算法链表逆置的两种方法_java实现链表的逆置算法_03

此时p指向N2，保存p的后继N3，再将N2尾插到链表L中，

java实现链表的逆置算法链表逆置的两种方法_链表_04

以此类推，直至保存后继的指针r为空，退出循环。

我把这种方法称为“冒泡法”，是因为算法流程和冒泡排序类似，只不过在冒泡排序中是相邻的元素出现逆序才交换，而链表逆置则要求每对结点之间都要交换顺序。

冒泡法和头插法不同，头插法只有一个工作指针p指向一个操作对象——被摘下来的结点，以及存储其后继的指针r。而冒泡法有两个工作指针，即一对工作指针，以及存储其后继的指针r，共计3个指针。考虑如下一般情况，

java实现链表的逆置算法链表逆置的两种方法_java实现链表的逆置算法_05

指针pre和p分别指向两个结点，将其看作一对结点，它们是每次循环操作的对象。循环中，让N2的后继指向N1，即完成了(N1,N2)的逆置。之后三个指针进一，pre=p，p=r，r=r->next，重复上述逆置操作，链表变成了下图。

java实现链表的逆置算法链表逆置的两种方法_链表_06

显而易见，如果指针，则循环还要继续下去，若，循环结束，链表逆置完成，而指针p指向逆置后的一个元素。

上述步骤发生的前提是链表中除了头结点以外，至少有两个结点，而为了将判断是否继续循环和是否进入循环结合起来，应将指针r初始置为指向第一个结点的后继，p指向第一个结点，即，指针pre无强制要求。

注意初始p指向的结点在完成逆置之后将成为最后一个结点，所以应该在逆置之前将p的后继置为空，否则逆置之后p的后继会指向倒数第二个结点，而倒数第二个结点的后继指向倒数第一个结点，即逆置前的p，两个结点之间形成环。