数据结构之链表与递归

绝地灬酷狼 2022-03-02 02:24 208阅读 0赞

### 文章目录 ###

*  链表与递归
 *   *  删除链表中的元素问题
     *  递归
     *  运用递归解决链表中删除元素的问题
     *  递归的微观解读
     *  递归算法的调试

# 链表与递归 #

## 删除链表中的元素问题 ##

LeetCode第203题

*  题目描述  
    删除链表中等于给定值 val 的所有节点。
 *  示例:  
    输入: 1->2->6->3->4->5->6, val = 6  
    输出: 1->2->3->4->5
 *  解答代码：

/**
     * Definition for singly-linked list.
     * public class ListNode { 
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {  val = x; }
     * }
     */ 
    class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
            while (head != null && head.val == val){ 
                ListNode delNode = head;
                head = head.next;
                delNode.next = null;
            }
    
            if(head == null)
                return null;
    
            // prev的值一定不是val了
            ListNode prev = head;
            while (prev.next != null){ 
                if (prev.next.val == val){ 
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                }else{ 
                    prev = prev.next;
                }
            }
            return head;
        
        }
    }

*  使用虚拟头结点的方式代码更加简洁

/**
     * Definition for singly-linked list.
     * public class ListNode { 
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {  val = x; }
     * }
     */ 
    class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
        	// 创建虚拟头结点
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
    
            ListNode prev = dummyHead;
            while (prev.next != null){ 
                if (prev.next.val == val){ 
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                }else{ 
                    prev = prev.next;
                }
            }
            return dummyHead.next;
        
        }
    }

*  测试自己的LeetCode链表代码  
    ListNode:

/**
     * Created by binzhang on 2019/3/18.
     */
    public class ListNode { 
        int val;
        ListNode next;
        ListNode(int x){ 
            val = x;
        }
    
        // 链表节点的构造函数
        // 使用arr为参数，创建一个链表，当前的ListNode为链表头结点
        public ListNode(int[] arr){ 
            if (arr == null || arr.length == 0)
                throw new IllegalArgumentException("arr can not be empty");
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1 ; i < arr.length ; i ++){ 
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }
    
        // 以当前节点为头结点的链表信息字符串
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null){ 
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }
    }
    
    Solution:
    /**
     * Created by binzhang on 2019/3/18.
     */
    public class Solution { 
        public ListNode removeElements(ListNode head, int val){ 
            while (head != null && head.val == val){ 
                ListNode delNode = head;
                head = head.next;
                delNode.next = null;
            }
    
            if(head == null)
                return null;
    
            // prev的值一定不是val了
            ListNode prev = head;
            while (prev.next != null){ 
                if (prev.next.val == val){ 
                    ListNode delNode = prev.next;
                    prev.next = delNode.next;
                    delNode.next = null;
                }else{ 
                    prev = prev.next;
                }
            }
            return head;
        }
    
        public static void main(String[] args) { 
            int[] nums = { 1,2,6,3,4,5,6};
            ListNode head = new ListNode(nums);
            // 因为在ListNode中重写了toString方法，所以会全部输出
            System.out.println(head);
    
            ListNode res = (new Solution()).removeElements(head,6);
            System.out.println(res);
        }
    }

输出：

1->2->6->3->4->5->6->NULL
    1->2->3->4->5->NULL

## 递归 ##

*  本质上，将原来的问题，转化为更小的同一问题
 *  举例：数组求和  
    Sum(arr\[0…n-1\]) = arr\[0\] + Sum(arr\[1…n-1\])
 *  手写一个数组求和

/**
     * Created by binzhang on 2019/3/18.
     */
    public class Sum { 
        public static int sum(int[] arr){ 
            return sum(arr, 0);
        }
    
        // 计算arr[l...n)这个区间内所有数字的和
        private static int sum(int[] arr, int l){ 
            if (l == arr.length)
                return 0;
            return arr[l] + sum(arr, l + 1);
        }
    
        public static void main(String[] args){ 
            int[] nums = { 1,2,3,4,5,6,7,8};
            System.out.println(sum(nums));
        }
    }

> 输出：36

*  链表具有天然的递归性  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]

## 运用递归解决链表中删除元素的问题 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]

*  递归解决删除链表元素问题

/**
     * Created by binzhang on 2019/3/18.
     */
    public class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
            if (head == null)
                return null;
    
    //        ListNode res = removeElements(head.next, val);
    //        if (head.val == val)
    //            return res;
    //        else { 
    //            head.next = res;
    //            return head;
    //        }
            head.next = removeElements(head.next, val);
            return head.val == val ? head.next : head;
        }
    
        public static void main(String[] args) { 
            int[] nums = { 1,2,6,3,4,5,6};
            ListNode head = new ListNode(nums);
            // 因为在ListNode中重写了toString方法，所以会全部输出
            System.out.println(head);
    
            ListNode res = (new Solution()).removeElements(head,6);
            System.out.println(res);
        }
    }

输出：

1->2->6->3->4->5->6->NULL
    1->2->3->4->5->NULL

## 递归的微观解读 ##

*  数组求和问题  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]
 *  删除链表元素问题  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 3]

## 递归算法的调试 ##

在每一次调用中加入输出更直观的了解递归算法的调用过程

/**
     * Created by binzhang on 2019/3/18.
     */
    public class Solution { 
        public ListNode removeElements(ListNode head, int val, int depth) { 
    
            String depthString = generateDepthString(depth);
    
            System.out.print(depthString);
            System.out.println("Call: remove " + val + " in " + head);
    
            if (head == null){ 
                System.out.print(depthString);
                System.out.println("Return: " + head);
                return head;
            }
    
            ListNode res = removeElements(head.next, val, depth + 1);
            System.out.print(depthString);
            System.out.println("After remove " + val + ": " + res);
    
            ListNode ret;
            if (head.val == val)
                ret = res;
            else{ 
                head.next = res;
                ret = head;
            }
    
            System.out.print(depthString);
            System.out.println("Return: " + ret);
            return ret;
        }
    
        private String generateDepthString(int depth){ 
            StringBuilder res = new StringBuilder();
            for (int i = 0 ; i < depth ; i ++)
                res.append("--");
            return res.toString();
        }
    
        public static void main(String[] args) { 
            int[] nums = { 1,2,6,3,4,5,6};
            ListNode head = new ListNode(nums);
            // 因为在ListNode中重写了toString方法，所以会全部输出
            System.out.println(head);
    
            ListNode res = (new Solution()).removeElements(head,6, 0);
            System.out.println(res);
        }
    }

输出：

1->2->6->3->4->5->6->NULL
    Call: remove 6 in 1->2->6->3->4->5->6->NULL
    --Call: remove 6 in 2->6->3->4->5->6->NULL
    ----Call: remove 6 in 6->3->4->5->6->NULL
    ------Call: remove 6 in 3->4->5->6->NULL
    --------Call: remove 6 in 4->5->6->NULL
    ----------Call: remove 6 in 5->6->NULL
    ------------Call: remove 6 in 6->NULL
    --------------Call: remove 6 in null
    --------------Return: null
    ------------After remove 6: null
    ------------Return: null
    ----------After remove 6: null
    ----------Return: 5->NULL
    --------After remove 6: 5->NULL
    --------Return: 4->5->NULL
    ------After remove 6: 4->5->NULL
    ------Return: 3->4->5->NULL
    ----After remove 6: 3->4->5->NULL
    ----Return: 3->4->5->NULL
    --After remove 6: 3->4->5->NULL
    --Return: 2->3->4->5->NULL
    After remove 6: 2->3->4->5->NULL
    Return: 1->2->3->4->5->NULL
    1->2->3->4->5->NULL

*  近乎和链表相关的所有操作，都可以使用递归的形式完成

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70]: /images/20220302/51c67ec1a588443fbfa84e27b4773bfa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 1]: /images/20220302/08d182d4cf1346d5ba34ef94664ebc06.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 2]: /images/20220302/214fe563ba2e47a6af9163559feadf81.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI0MDk1MDU1_size_16_color_FFFFFF_t_70 3]: /images/20220302/8219cdcc53b4469089dc16e216469f26.png