[数据结构与算法]单链表反转（迭代和递归）

单链表反转

一、迭代实现；

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:不可以，会导致双向链表。