递归]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;}
};
更多推荐
[链表][递归]leetcode206:反转链表(easy)
发布评论