LeetCode 剑指 Offer 06 反转链表/从尾到头打印链表[递归/栈]-一一网

这是我参与更文挑战的第 6 天，活动详情查看：更文挑战

反转链表

题目描述

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例 1：

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
复制代码

限制

0 <= 节点个数 <= 5000

思路分析

链表反转的题目我们之前也遇到过，这次使用的是递归解法，链表+递归，在算法中这两类题目都挺难写。递归解法要先找到递归的终止条件，然后将大问题分解化解为小问题，总结出这些问题的一般规律。

我们首先先考虑边界问题，如果该链表是空节点，那么直接返回。

举例来说，链表是 1->2->3->4->5，我们先找到反转链表的最后一个节点ListNode newHead = reverseList(head.next)，对最后一个节点进行反转head.next.next = head;，最后一个节点的前继节点的 next 指向 null，即head.next = null，然后返回反转之后的新头结点，就是 newHead。

不断递归，因为每次递归反转的头结点都是 5，所以最终返回的头结点是 newHead。

代码展示

解法一：时间复杂度是 ${O(2^n)}$ ，空间复杂度是 ${O(1)}$ 。

    public ListNode reverseList(ListNode head) { //1-2-3-4-5

        if (head == null){ //为null的情况
            return head;
        }

        if (head.next == null){
            return head;
        }
        ListNode newNode = reverseList(head.next);

        head.next.next = head;  //4.next.next = 4      5.next = 4
        head.next = null;
        return newNode;

    }
复制代码

运行后，提示成功

解答成功:
				执行耗时:0 ms,击败了100.00% 的Java用户
				内存消耗:38.4 MB,击败了17.56% 的Java用户
复制代码

小结

递归，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决，子问题再拆解成子子问题，…，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,….,直到最开始的问题解决。

从尾到头打印链表

题目描述

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]
复制代码

限制

0 <= 链表长度 <= 10000

思路分析

从尾到头打印链表，很容易就让人想起递归解法，一直判断是否是尾部，如果不是尾部，继续下一个链表，这种类型的问题是很容易用递归进行解答的。同时我们需要一个列表存储链表中的数据，然后再放到数组中。

当然我们还可以用栈来解答这道题，利用栈的先进后出的特点，先遍历链表入栈，然后再出栈，就可以从尾到头打印链表了。

代码展示

解法一：时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

    List<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        recursion(head);
        int[] temp = new int[list.size()];
        for (int i = 0;i < list.size();i++){
            temp[i] = list.get(i);
        }
        return temp;
    }

    public void recursion(ListNode p){
        if (p == null){
            return;
        }
        recursion(p.next);
        list.add(p.val);
    }
复制代码

解法二：遍历链表，利用栈先进后出的特点，时间复杂度是 ${O(n)}$ ，空间复杂度是 ${O(n)}$ 。

    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        if (head == null){
            return new int[0];
        }
        while (head != null){
            stack.push(head.val);
            head = head.next;
        }
        int size = stack.size();
        int[] arr = new int[size];
        int i = 0;
        while (!stack.isEmpty()){
            arr[i++] = stack.pop();
        }
        return arr;
    }
复制代码