[剑指 Offer 第 2 版第 6 题] “从尾到头打印链表”做题记录

第 6 题：从尾到头打印链表

传送门：AcWing：从尾到头打印链表，牛客网 online judge 地址。

输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

样例：

输入：[2, 3, 5] 返回：[5, 3, 2]

分析：

使用栈来解决这个问题应该很容易想到的。
既然使用了栈，递归求解就成为了一个思路。

思路1：首先应该想到，使用栈作为辅助。

Python 代码1：Python 中的列表有可以在指定位置插入元素，我们就每次在索引 $0$ 处插入元素好了

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution(object):

        def printListReversingly(self, head):
            """
            :type head: ListNode
            :rtype: List[int]
            """
            p = head
            stack = []
            while p:
                stack.append(p.val)
                p = p.next
            return stack[::-1]

Python 代码2：

  # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    class Solution(object):

        def printListReversingly(self, head):
            """
            :type head: ListNode
            :rtype: List[int]
            """
            p = head
            stack = []
            while p:
                stack.insert(0, p.val)
                p = p.next
            return stack

Java 代码：使用栈辅助完成

  import java.util.ArrayList;
    import java.util.Stack;

    class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class Solution {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> res = new ArrayList<>();
            if (listNode == null) {
                return res;
            }
            Stack<Integer> stack = new Stack<>();
            ListNode curNode = listNode;
            while (curNode != null) {
                stack.add(curNode.val);
                curNode = curNode.next;
            }
            while (!stack.isEmpty()) {
                res.add(stack.pop());
            }
            return res;
        }
    }

思路2：使用递归，关键在于递归函数的编写，特别注意：在回溯的时候，添加当前结点的值到结果集中。

Python 代码：

  class Solution(object):

        def printListReversingly(self, head):
            """
            :type head: ListNode
            :rtype: List[int]
            """
            res = []
            self.helper(res, head)
            return res

        def helper(self, res, listnode):
            if listnode is None:
                return
            # 应该先判断下一个结点是否为空，如果不为空，则递归调用，在回溯的时候，才添加到结果中
            if listnode.next:
                self.helper(res, listnode.next)
            # 这一步特别关键：回溯时添加
            res.append(listnode.val)

Java 代码：

  import java.util.ArrayList;

    public class Solution2 {
        public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
            ArrayList<Integer> res = new ArrayList<>();
            if (listNode == null) {
                return res;
            }
            printListFromTailToHead(listNode, res);
            return res;
        }

        private void printListFromTailToHead(ListNode listNode, ArrayList<Integer> res) {
            if (listNode == null) {
                return;
            }
            // 写在这个位置，就是正序
            if (listNode.next != null) {
                printListFromTailToHead(listNode.next, res);
            }
            // 写在这个位置，就是倒序
            res.add(listNode.val);
        }
    }

思考下面这个写法为什么是错的。