Java教程

单链表反转(迭代和递归)

本文主要是介绍单链表反转(迭代和递归),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

单链表反转

一、迭代实现;

  1. 新建两指针,curr和prev
 ListNode* curr=head;
 ListNode* prev=NULL;

2.向前递进条件是curr不为NULL的时候

while(curr){
	ListNode*temp=curr->next; //这里要先把下一个记录下来
	curr->next=prev;
	prev=curr;
	curr=temp;
}
return prev;

迭代代码逐行演示

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

二、递归实现

1临界条件,因为一个节点或者无节点的时候,没有反转,返回的就是head

head==NULL||head->next==NULL;

2.f函数就是递归函数,它有一个参数

if(head==NULL||head->next==NULL)
return head;
ListNode* Myhead=f(head->next);
head->next->next=head;
head->next=NULL;
return Myhead;

递归实现逐步演示

1.递到最后是这一种情况。在这里插入图片描述
2.然后将head的下一个节点指向head 也就是head->next->next=head;
我们还要把head指向null,避免双向链表

在这里插入图片描述
3.然后一直向前归。按照第2步,我们只要把蓝色边框包裹的看成一个节点就方便理解了。
在这里插入图片描述

# 总结与思考
Q1:迭代实现中prev=curr和curr=temp;能不能交换位置?
A1:不可以,如交换位置,curr原来的值没有保存,prev得到的是temp,无意义。
Q2:递归实现中head->next能不能去掉?
A2:不可以,会导致双向链表。

这篇关于单链表反转(迭代和递归)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!