链表与递归

/ 数据结构与算法 / 0 条评论 / 2225浏览

引言

数学归纳法: 用于证明断言对所有自然数成立

例如

如题:1+2+3+...+n=n(n+1)/2

数学归纳法与程序

那么我们直接将其翻译为程序设计语言

    int sum(int n) {
        if (n == 1) return 1;
        return sum(n - 1) + n;
    }

递归

程序调用自身的编程技巧称为递归(recursion)。

每个递归定义必须至少有一个条件,满足时递归不再进行,既不再引用自身而是返回值推出。

递归控制

利用数学归纳法的思想,在 n-1 时函数可以正常工作在 n 时也一定成立

如何证明递归函数正确执行

我们在写递归函数的过程就是证明递归函数正确性的证明

递归书写

这是我书写递归的核心思想

链表与递归

链表这种数据结构拥有天然递归结构性质,近乎和链表相关的所有操作,都可以使用递归的形式完成。

下面列出三个比较经典的例子来展示如何使用递归完成链表的操作:

例一:创建链表

输入一个数组,将其中的元素以链式存储

代码

首先定义链表的节点类型(Node),后面的例子会复用这个类

public class Node {

    private final int value;
    private Node next;

    public Node(int value) {
        this.value = value;
        // 保证每次创建的Node都是干净的
        this.next = null;
    }

    public int getValue() {
        return value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public static void printLinkedList(Node head) {
        while (head != null) {
            System.out.print(head.getValue());
            System.out.print(" ");
            head = head.getNext();
        }
        System.out.println();
    }
}

使用递归的方式创建链表

    public Node createLinkedList(List<Integer> data) {
        if (data.isEmpty()) {
            return null;
        }

        Node head = new Node(data.get(0));
        Node linkedList = createLinkedList(data.subList(1, data.size()));// subList: 若起始下标等于截止下标则返回null
        head.setNext(linkedList);
        return head;
    }

测试用例

    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();

        Node.printLinkedList(
                creator.createLinkedList(new ArrayList<Integer>())
        );

        Node.printLinkedList(
                creator.createLinkedList(Arrays.asList(1))
        );

        Node.printLinkedList(
                creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5))
        );

    }

例二:链表反转

这是我们需要进行反转的链表,下面是我们希望的结果

我们不管首元节点,调用reverseLinkedList方法逆置剩下所有节点(不从首元开始是因为首元很有很多边界条件)

得到一条新的链表,使其指向首元节点,再让首元节点指向null

代码

    public Node reverseLinkedList(Node head) {

        if (head == null || head.getNext() == null) {
            return head;
        }

        // 反转除首元素节点外的其他节点
        Node newHead = reverseLinkedList(head.getNext());
        // 使第二个节点指向首元素节点
        head.getNext().setNext(head);
        // 首节点指向null
        head.setNext(null);
        return newHead;
    }

测试用例

    public static void main(String[] args) {
        LinkedListCreator creator = new LinkedListCreator();
        LinkedListReverser reverser = new LinkedListReverser();

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(new ArrayList<Integer>())));

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1)))
        );

        Node.printLinkedList(reverser.reverseLinkedList(
                creator.createLinkedList(Arrays.asList(1, 2, 3, 4, 5)))
        );
    }

例三:列出所有组合

这是一道经典例题:

题目:从一组数中选 n 个进行组合
eg: combinations([1,2,3,4],2) 从1,2,3,4中任选 2 个数进行组合

如下结果:
[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]

分析:

要点

代码

    public void combinations(List<Integer> selected, List<Integer> data, int n) {

        if (n == 0) {
            // output all selected elements
            for (Integer integer : selected) {
                System.out.print(integer);
                System.out.print(" ");
            }
            System.out.println();
            return;
        }
        if (data.isEmpty()) {
            return;
        }

        // select element 0
        selected.add(data.get(0));
        combinations(selected, data.subList(1, data.size()), n - 1);

        // unSelect element 0
        selected.remove(selected.size() - 1);
        combinations(selected, data.subList(1, data.size()), n);
    }

测试用例

    public static void main(String[] args) {
        Combinations comb = new Combinations();

        System.out.println("Testing normal data.");
        comb.combinations(
                new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 2);
        System.out.println("==========");

        System.out.println("Testing empty source data.");
        comb.combinations(
                new ArrayList<>(), new ArrayList<>(), 2);
        System.out.println("==========");
        comb.combinations(
                new ArrayList<>(), new ArrayList<>(), 0);
        System.out.println("==========");

        System.out.println("Selecting 1 and 0 elements.");
        comb.combinations(
                new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 1);
        System.out.println("===========");
        comb.combinations(
                new ArrayList<>(), Arrays.asList(1, 2, 3, 4), 0);
        System.out.println("===========");

        System.out.println("Testing large data");
        comb.combinations(
                new ArrayList<>(),
                Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10), 4);
    }

递归的缺点

提示:完整代码放在了我的 gitee 上面