递归魔法

LeetCode 206 反转链表 2023.12.26

• 题目链接
• labuladong讲解[链接]
  

ListNode* reverseList(ListNode* head) {//递归退出条件if(head == NULL || head->next == NULL)return head;//递归ListNode* last = reverseList(head->next);//处理head->next->next = head;//指向反转head->next = NULL;//指向最后空指针return last;//返回链表最后一个节点
}

---

LeetCode 92 反转链表-ii 2023.12.26

• 题目链接
• labuladong讲解[链接]
  

class Solution {
public://反转区间链表的递归函数ListNode* reverseBetween(ListNode* head, int left, int right) {//遍历区间元素，递归退出条件，//当从head开始反转时，直接进入从头反正right个元素的递归函数if(left == 1)return reverseN(head, right);//head指向的下一个元素来自下一次递归，起始元素是head->next,区间是left-1，right-1head->next = reverseBetween(head->next, left-1, right-1);return head;}//用来记录后面不翻转的第一个节点ListNode* successor = NULL;//反转从head开始right个节点的递归函数ListNode* reverseN(ListNode* head, int right){//递归退出条件，当反转的节点为一个(为head节点)时，//记录后面不翻转的第一个节点，并返回当前反转后的head节点if(right == 1){successor = head->next;return head;}//记录反转后的首节点ListNode* last = reverseN(head->next, right-1);//反转中间节点head->next->next = head;head->next = successor;//返回反转后的首节点return last;}
};