1. 首页
  2. 剑指offer经典面试题

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

[剑指 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);
        }
    }

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

liwei20191016_1.png

拿具体的测试用例就可以很容易想明白,不能使用 if else 语句。

liwei20191015_2.png

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3255.html

« [剑指 Offer 第 2 版第 5 题] “替换空格”做题记录
[剑指 Offer 第 2 版第 7 题] “重建二叉树”做题记录»

相关推荐

QR code