[链表][递归]leetcode206：反转链表(easy)

递归]leetcode206：反转链表(easy)"/>

[链表][递归]leetcode206：反转链表(easy)

题目：

题解：

解法1：迭代法
使用两个指针来完成反转，pre表示前驱节点，cur表示当前，每次循环我们需要先保存cur的next节点，然后反转cur和pre，直到cur为nullptr为止。

---

解法2：递归法

• 1）递归边界：当head为空节点或单个节点时，返回head节点
• 2）单次过程：head->next->next=head表示为由head->Next变为head<-->Next，然后断开head->Next即将head->next赋为nullptr，现在就完成两个节点的反转了即由head->Next变为head<-Next了。
• 3）返回值p指向未反转子链表的表首。最终链表全部反转完成，p指向原始链表的尾节点，即反转链表的首节点。

代码如下：

class Solution {
public://解法1：迭代法ListNode* reverseList(ListNode* head) {if(nullptr==head||nullptr==head->next)return head;//pre为前驱节点，cur为当前节点，每次循环我们需要将cur连上pre，直到cur为空，表示反转结束ListNode *pre=nullptr,*cur=head;while(cur){ListNode *nxt=cur->next;cur->next=pre;pre=cur;cur=nxt;}return pre;}//解法2：递归法ListNode* reverseList_2(ListNode *head){//1:递归边界if(nullptr==head||nullptr==head->next)return head;//2、递归函数式子：一直到链表尾部才开始反转ListNode *p=reverseList(head->next);//将head->next节点连上它的前驱节点head，同时将head原始方向(->)断开，也就是head->next赋为nullptrhead->next->next=head;head->next=nullptr;return p;}
};