递归算法 - zhpanvip/AndroidNote GitHub Wiki

206. 反转链表

/**
 * 递归法
 * 递归的递流程直接找到递归的最后一个节点，最后一个节点的next为null,返回自身，然后开始递归的归流程
 * 递归的归流程，从最后一个节点向上回溯，将最后一个节点的next指向倒数第二个节点，倒数第二个节点的next指向null
 * 以此回溯到第一个节点完成链表的反转
 */
public static ListNode reverseLink2(ListNode head) {
    // head == null这个条件一定要判断啊！！！！
    if (head == null || head.next == null) {
        return head;
    }
    // 返回最后一个节点
    ListNode lastNode = reverseLink2(head.next);
    head.next.next = head;
    head.next = null;
    return lastNode;
}

206 反转链表 扩展

public static ListNode cursor;

public static ListNode reverseLink(ListNode head, int n) {
    if (n == 1) {
        cursor = head.next;
        return head;
    }
    ListNode lastNode = reverseLink(head.next, n - 1);
    head.next.next = head;
    head.next = cursor;
    return lastNode;
}

92. 反转链表 II

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null) {
        return head;
    }
    return reverse(head, left, right);
}

private ListNode reverse(ListNode head, int left, int right) {
    if (left == 1) {
        return LeetCode92$.reverseLink(head, right);
    }
    head.next = reverse(head.next, left - 1, right - 1);
    return head;
}

21. 合并两个有序链表

/**
 * 递归法
 */
public ListNode mergeTwoList2(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    } else if (l2 == null) {
        return l1;
    } else {
        if (l1.val < l2.val) {
            l1.next = mergeTwoList2(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoList2(l1, l2.next);
            return l2;
        }
    }
}

快速排序

/**
 * 快速排序
 * <p>
 * 核心的思路是取第一个元素（或者最后一个元素）作为分界点，把整个数组分成左右两侧，左边的元素小于或者等于分界点元素，
 * 而右边的元素大于分界点元素，然后把分界点移到中间位置，对左右子数组分别进行递归，最后就能得到一个排序完成的数组。
 * 当子数组只有一个或者没有元素的时候就结束这个递归过程。
 */
public static void quickSort(int[] nums, int left, int right) {
    if (left > right) return;
    int key = nums[left];
    int l = left;
    int r = right;
    while (l < r) {
        while (nums[r] >= key && l < r)
            r--;
        while (nums[l] <= key && l < r)
            l++;
        if (l < r)
            swap(nums, r, l);
    }

    nums[left] = nums[r];
    nums[r] = key;

    quickSort(nums, left, r - 1);
    quickSort(nums, r + 1, right);
}