玩转数据结构4-链表与递归

2019-10-12  本文已影响0人  xkzhai

上一节课主要学习了一种具有真正动态数据结构的数据结构——链表，实现了链表基本的增删改查等操作，基于链表的操作特性，实现了栈的结构，并通过增加尾节点，进一步实现了队列这样一种数据结构。本节课从leetcode的一个练习题出发，研究链表具有的一种天然属性——递归。

1. leetcode上的问题

问题描述：在链表中删除值为val的所有节点,，返回删除后的链表头节点

1.1 解题方案1（不使用虚拟头节点）

不使用虚拟头节点，从头节点出发：

public ListNode removeElements(ListNode head, int val) {
    // 如果头节点不为空，且数据恰好为需要删除的元素，则删除头节点
    // 使用while循环，处理前面多个节点均为待删除元素的情况
    while(head!=null && head.val == val) {
        ListNode delNode = head;
        head = head.next;
        delNode.next = null;
        // head = head.next;
    }
    
    // 如果头节点为空，则直接返回空节点
    if(head == null){
        return null;
    }
    
    // 如果头节点不为空，且不为待删除元素，则遍历余下的链表元素
    // 需找到待删除元素的前一节点
    ListNode prev = head;
    while(prev.next!=null) {
        if(prev.next.val == val) {
            ListNode delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            // prev.next = prev.next.next;
        }
        else {
            prev = prev.next;
        }
    }
    return head;
}
1.2 解决方案2（使用虚拟头节点）

同样地，使用虚拟头节点可以避免单独处理 1）头节点为空； 2）头节点为待删除元素的特殊情况，所有情况的删除逻辑保持一致。找到满足条件的待删除节点的前一节点，然后删除即可。

  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) {
                prev.next =  prev.next.next;
            }
            else {
                prev = prev.next;
            }
        }
        return dummyHead.next;
    }
1.3 测试解决方案

2. 递归

2.1 递归的宏观语意

递归的本质是将原来的问题转化为更小的同一问题，以数组求和为例

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[] arr = {1,2,3,4,5};
        System.out.println(sum(arr)); // 15
    }
}

链表具有天然的递归性，一个链表完全可以用一个头节点和一个更短的链表来描述：


链表的天然递归性
2.2 解决方案3（使用递归）

假设要删除下述链表中的某些元素：


image.png 
public ListNode removeElements(ListNode head, int val) {
    // 如果头节点为空，返回空节点
    if(head==null) {
        return null;
    }

    // 如果头节点不为空，删除更短链表中对应的元素，记返回的链表头节点为res
    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;
}
2.3 递归的微观语意

递归的实质是函数的调用，只不过递归是函数调用函数本身，以数组求和为例：

对链表删除元素也是一样的，模拟删除如下链表中的7:


LinkedList 
removeElements(head,int val){
    if(head==null) return null;
    head.next = removeElements(head.next,val);
    return head.val == val? head.next:head;
}

3. 递归程序的调试

对递归程序，一个可行的调试方法是用ide自带的Debug功能，跟踪程序运行的过程，观察运行过程中变量的变化情况。这里介绍一种通过打印一些输出信息来判断递归程序是否正常运行的方法。

这种调试方法的基本思想是，函数每调用自身一次，深度+1，函数每返回一次，深度-1，通过构造基于深度信息的特殊字符串，可以将处于同一深度的输入输出数据打印出来，观察递归执行过程中是否存在问题。

4. 总结

本节课主要介绍了递归的思想，结合链表的天然递归性，使用递归方法完成了链表元素的删除操作。递归的本质是把原问题转化为一个更小的同一问题，关键在于边界位置的处理以及如何进行转化。之后的课程将会涉及到大量的递归操作，多写多用，慢慢掌握其中技巧。

上一篇 下一篇

猜你喜欢

热点阅读