剑指offer——链表

ゝ一纸荒年。 2021-09-21 07:52 271阅读 0赞

题目3：输入一个链表，按链表从尾到头的顺序返回一个ArrayList [题目][Link 1]

解题思路：

用stack方式是比较容易想到的，递归的方式比较难以想到

递归的关键，先向下递归再执行本次操作，这样才会形成反序操作序列(反序操作序列)

/**
    *    public class ListNode {
    *        int val;
    *        ListNode next = null;
    *
    *        ListNode(int val) {
    *            this.val = val;
    *        }
    *    }
    *
    */
    
    //1.ArrayList实现
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      ArrayList<Integer> list=new ArrayList<Integer>();
      while(listNode!=null){
        list.add(0,listNode.val);
        listNode=listNode.next;
      }
      return list;
    }
    //2.stack
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      ArrayList<Integer> list=new ArrayList<Integer>();
      Stack<Integer> stack=new Stack<Integer>();
      while(listNode!=null){
        stack.push(listNode.val);
        listNode=listNode.next;
      }
      while(!stack.empty()){
        list.add(stack.pop());
      }
      return list;
    }
    //3.递归(递归的关键，先向下递归再执行本次操作，这样才会形成反序操作序列)
    ArrayList<Integer> list=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
      ArrayList<Integer> list=new ArrayList<Integer>();
      while(listNode!=null){//递归结束
        printListFromTailToHead(listNode.next);
        list.add(listNode.val);//关键(将最后一个数据放入)
      }
    }

[Link 1]: https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

发表评论取消回复

表情：

评论列表（有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer 合并链表

合并排序好的两个链表，同样需要注意一下问题：代码鲁棒性（对NULL等特殊输入有对应）代码正确性（没有链表断裂的情况）对于链表的大量指针操作，一定要将指

不念不忘少年蓝@/ 2023年10月17日 16:56/ 0 赞/ 61 阅读

相关剑指offer_链表逆置

/ 反转链表并输出反转后链表的头结点与从尾到头打印链表还不一样，打印不需要改变链表结构初步思路：重建链表，与原来的反向，可行吗？将节点从头到

电玩女神/ 2022年06月09日 14:06/ 0 赞/ 141 阅读

相关剑指offer:反转链表

题目描述输入一个链表，反转链表后，输出新链表的表头。 class Solution { public: ListNode Revers

Bertha 。/ 2022年04月10日 07:54/ 0 赞/ 187 阅读

相关【剑指Offer】（链表）反转链表

题目链接：[https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&tqId=11

柔光的暖阳◎/ 2022年03月17日 14:22/ 0 赞/ 135 阅读

相关剑指Offer-反转链表

题目描述输入一个链表，反转链表后，输出新链表的表头。最优解：使用两个指针，一个存储原链表的后续内容，一个用来存储当前的反转链表。循环存储是核心！最优解

痛定思痛。/ 2022年02月28日 15:36/ 0 赞/ 177 阅读

相关剑指offer-反转链表

题目描述输入一个链表，反转链表后，输出新链表的表头。实现思想有以下几种实现思想。我用的实现思想（第一种）：利用栈的原理，申请一个节点栈，将链表上的节点

你的名字/ 2022年02月14日 09:19/ 0 赞/ 222 阅读

相关【剑指offer】反转链表

题目描述输入一个链表，反转链表后，输出新链表的表头。【分析】关于链表的题目虽然简单，但很容易出错。这道题比较不容易出错的办法是，单独定义一个新节点NewH，当找到

旧城等待，/ 2022年01月28日 07:51/ 0 赞/ 214 阅读

相关【剑指offer】反转链表

题目描述：输入一个链表，反转链表后，输出新链表的表头。思路分析：当前节点为head，反转链表应该将当前节点的下个节点next指向当前节点，而当前节点的next则为p

太过爱你忘了你带给我的痛/ 2021年11月08日 22:20/ 0 赞/ 289 阅读

相关剑指offer——链表

题目3：输入一个链表，按链表从尾到头的顺序返回一个ArrayList [题目][Link 1] 解题思路：用stack方式是比较容易想到的，递归的方式比较难以想到递归

ゝ一纸荒年。/ 2021年09月21日 07:52/ 0 赞/ 272 阅读

相关剑指offer：反转链表

试题：输入一个链表，反转链表后，输出新链表的表头。代码：至少需要两个指针存储前后节点，然后发现还缺一个指针存储下下个节点。所以总共需要三个指针。 /

红太狼/ 2021年06月24日 16:00/ 0 赞/ 381 阅读