从力扣[203]理解递归思想

深碍√TFBOYSˉ_ 2024-02-21 11:54 123阅读 0赞

> 本文旨在通过使用递归方法的使用来进一步了解递归思想

![64c759c4a9de41f291ccaa94a21694e9.png][]

class Solution {
        public ListNode removeElements(ListNode head, int val) {
            if (head == null) {
                return head;
            }
            head.next = removeElements(head.next, val);
            return head.val == val ? head.next : head;
        }
    }

既然要使用递归算法，那么就要对于递归有一定的了解：

## 递归的三个特点 ##

1.  有终止条件
2.  自身调用
3.  从上往下解决问题

## “有终止条件” ##

在本题中，终止条件就是head == null。

一个节点接一个节点地往后判断，当后移一位时节点变为null时，说明已经到链表末尾了。递归结束，

## “自身调用”与“从上到下” ##

对于本题中 removeElements(ListNode head, int val) 方法的含义是：获取-对于给定的头节点为head的链表，删除节点值为val的节点后-的新的头节点

对于第一个节点来说，以它为头节点的链表经过删除后的新的头节点要么是它本身，要么是它后面一长串链表的头节点。

即 removeElements(head.next, int val)

于是我们就达到了“自身调用”和“从上到下”的要求

## 代码解析 ##

public class LC01 {
         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 removeElements(ListNode head, int val) {
                //终止条件
                if (head == null) {
                    return head;
                }
                //自身调用
                head.next = removeElements(head.next, val);
                //如果head的节点值为val，那么新的头节点为head.next，否则为head
                return head.val == val ? head.next : head;
            }
        }
    
    }

[64c759c4a9de41f291ccaa94a21694e9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/9424ab110f584be0804f11c09d8244e4.png