链表与递归

• 定义
• 设计递归函数的2个步骤
• 链表的天然递归性
  • 使用递归实现删除链表的元素
• 递归的调试方法

定义

• 本质上, 将原来的问题, 转化为更小的同一问题
  

• 理解递归, 需要掌握临界条件, 识别出最小的处理单元, 然后当做一个普通的函数调用自己就行
  

设计递归函数的2个步骤

链表的天然递归性

image.png

使用递归实现删除链表的元素

public class ListNode {

    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }

}

public class Solution3 {

    public ListNode removeElements(ListNode head, int val) {

        if (head == null) {
            return head;
        }

        ListNode res = removeElements(head.next, val);

        if (head.val == val) {
            return res;
        }else {
            head.next = res;
            return head;
        }
    }

    public ListNode removeElements1(ListNode head, int val) {

        if (head == null) {
            return head;
        }

        return head.val == val ? head.next : head;
    }
}

递归的调试方法