1 迭代反转
3个指针,beg,mid,end;如图所示:
3 个指针每次各向后移动一个节点,直至 mid 指向链表中最后一个节点(此时 end 为 NULL )。需要注意的是,这 3 个指针每移动之前,都需要做一步操作,即改变 mid 所指节点的指针域,另其指向和 beg 相同。
1) 在图 3 的基础上,我们先改变 mid 所指节点的指针域指向,另其和 beg 相同(即改为 NULL),然后再将 3 个指针整体各向后移动一个节点。整个过程如图 4 所示:
2) 在图 4 基础上,先改变 mid 所指节点的指针域指向,另其和 beg 相同(指向节点 1 ),再将 3 个指针整体各向后移动一个节点。整个过程如图 5 所示:
3) 在图 5 基础上,先改变 mid 所指节点的指针域指向,另其和 beg 相同(指向节点 2 ),再将 3 个指针整体各向后移动一个节点。整个过程如图 6 所示:
4) 图 6 中,虽然 mid 指向了原链表最后一个节点,但显然整个反转的操作还差一步,即需要最后修改一次 mid 所指节点的指针域指向,另其和 beg 相同(指向节点 3)。如图 7 所示:
注意,这里只需改变 mid 所指节点的指向即可,不用修改 3 个指针的指向
5) 最后只需改变 head 头指针的指向,另其和 mid 同向,就实现了链表的反转
//迭代反转法,head 为无头节点链表的头指针
link* reverse(link* head)
{
if(head ==NULL || head->next == NULL)
return head;
link* beg = NULL;
link* mid = head;
link* end = head->next;
//遍历
while(1)
{
//修改mid所指节点的指向beg
mid->next = beg;
//判断end是否最后了
if(end == NULL)
break;
//调整向后移动
beg = mid;
mid = end;
end = end->next;
}
//修改head头指针的指向
head = mid;
return head;
}
2 头插
所谓头插法,是指在原有链表的基础上,依次将位于链表头部的节点摘下,然后采用从头部插入的方式生成一个新链表,则此链表即为原链表的反转版
link * reverse(link * head) {
link * new_head = NULL;
link * temp = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
while (head != NULL)
{
temp = head;
//将 temp 从 head 中摘除
head = head->next;
//将 temp 插入到 new_head 的头部
temp->next = new_head;
new_head = temp;
}
return new_head;
}
3 就地逆转
就地逆置法和头插法的实现思想类似,唯一的区别在于,头插法是通过建立一个新链表实现的,而就地逆置法则是直接对原链表做修改,从而实现将原链表反转
值得一提的是,在原链表的基础上做修改,需要额外借助 2 个指针(假设分别为 beg 和 end)。仍以图 1 所示的链表为例,接下来用就地逆置法实现对该链表的反转:
link * reverse(link * head) {
link * beg = NULL;
link * end = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
beg = head;
end = head->next;
while (end != NULL) {
//先将end节点的下一节点接上beg节点,将 end 从链表中摘除
beg->next = end->next;
//将 end 移动至链表头
end->next = head;
head = end;
//调整 end 的指向,另其指向 beg 后的一个节点,为反转下一个节点做准备
end = beg->next;
}
return head;
}
4 递归反转(限无头节点)
这里相当于每次压栈,进入一个节点,到最后节点的时候,开始出栈,并进行一个链表反转操作
link* reverse(link* head) {
//递归的出口
if (head == NULL || head->next == NULL) // 空链或只有一个结点,直接返回头指针
{
return head;
}
else
{
//一直递归,找到链表中最后一个节点
link *new_head = reverse(head->next);
//当逐层退出时,new_head 的指向都不变,一直指向原链表中最后一个节点;
//递归每退出一层,函数中 head 指针的指向都会发生改变,都指向上一个节点。
//每退出一层,都需要改变 head->next 节点指针域的指向,同时令 head 所指节点的指针域为 NULL。
head->next->next = head;
head->next = NULL;
//每一层递归结束,都要将新的头指针返回给上一层。由此,即可保证整个递归过程中,能够一直找得到新链表的表头。
return new_head;
}
}