剑指offer——3.从尾到头打印链表

本文主要是介绍剑指offer——3.从尾到头打印链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/

---

 

自己用了两种方法

1. 利用list的add(int index, E element)方法，遍历链表，每次插入到索引为0的位置。

public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {ArrayList<Integer> list = new ArrayList<Integer>();if (null == listNode) {return list;}ListNode now = listNode;// 当前遍历结点while (now != null) {list.add(0, now.val);now = now.next;// 修改当前结点为下一个}return list;}

(后来才想到自带的Collections逆序方法，直接add向后添加到list然后reverse也可以的）

 

2. 定义一个头结点，然后一个一个向前插入🤭思路稍微有点点绕。先附代码：

public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {ArrayList<Integer> list = new ArrayList<Integer>();if (null == listNode) {return list;}ListNode head = null;// 头结点ListNode now = listNode;// 当前遍历结点while (now != null) {ListNode temp = new ListNode(now.val);if(head == null){head = temp;}else{temp.next = head;// 把头结点放在下一节点的下一个head = temp;// 让下一个结点为头结点}now = now.next;// 修改当前结点为下一个}now = head;while (now != null) {list.add(now.val);now = now.next;// 修改当前结点为下一个}return list;}

      1） 定义一个头结点，一个now节点作为遍历的当前结点

      2） 遍历传入的链表，拿到当前结点，定义为一个新的结点temp，temp的val为当前结点的val，next为空。

      3） 如果此时头结点为空，则将这个新的结点作为头结点，否则将temp的next指向当前的头结点，也就是将这个结点插入到头结点前方。

      4） 然后将这个temp修改为头结点，遍历到下一个节点的时候，则会继续向temp前面插入结点

      5） 每次修改now结点为next，否则会死循环

      6） 遍历完成后，再将新建出来的链表正向循环一次逐个插入list中

 

由于Stack的使用还没有学习到，所以只想到了上述两种方法。后来看别人的思路时，比较好的是栈和递归两种：

3. 栈的简单运用

链接：https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035?answerType=1&f=discussion
来源：牛客网public ArrayList printListFromTailToHead(ListNode listNode) {    ArrayList list = new ArrayList();    Stack stack = new Stack();    while (listNode != null) {        stack.push(listNode.val);        listNode = listNode.next;    }    while (!stack.empty()) {        list.add(stack.pop());    }    return list;
}

4. 递归——😔看完之后真是恍然大悟，锤胸顿足，悔恨交加啊~！

public ArrayList printListFromTailToHead(ListNode listNode) {        if(listNode!=null){            printListFromTailToHead(listNode.next);            list.add(listNode.val);        }        return list;    
}

 

这篇关于剑指offer——3.从尾到头打印链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---