今天说一下这个算法(一) 递归

递归的核心：对于一个节点来说，它只需要知道它之后的所有节点操作之后的结果就可以了。

个人总结三要素：

  • 确定递归函数的参数和返回值。
  • 确定终止条件。
  • 确定单个递归的内容。

例题

1，反转链表（递归，双指针 ）

来自 LeetCode206

补充：

* public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }

解法

1，双指针/迭代

在双指针文章里。

2，递推

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }

    public ListNode reverse(ListNode pre,ListNode cur){
        if(cur == null)
            return pre;
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(cur,temp);
    }
}

pre为前项，cur为当前指针，temp为后项。

理解（不保证正确）

1，递归想对于迭代，代码会更加清晰一些。

2，递归分两种

  • 一种是return 递归式，求的是最后一个递归式的结果，作为整个函数的结果。
  • 一种是过程中递归式，更多是类似于动态规划，每一层递归都是给前一阵作为实现的基石。
  • 递归思想中，不应该考虑每一步递归的过程，这样大概率出错。应该考虑当前递归我需要得到的结果就可以了。（重点）

3，有关链表的题目，应该在本子上进行画图，会让思路更加清晰。

2,合并两个有序链表

来自LeetCode 21

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val>l2.val)
        {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
        else
        {
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

理解

1，想到用递归做题有点难，想到后就很容易解决。

3，二叉树遍历

在算法(八)那篇文章里。

很重要。（不过递归算法太简单不是很重要)

正文完
2022-04-14