[剑指Offer]面试题3：使用Java实现从链表尾部到头部的打印功能（基于栈结构）

【问题描述】

输入一个链表&＃xff0c;按链表从尾到头的顺序返回一个ArrayList。

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


【解答思路】

1.ArrayList遍历接收&＃xff0c;翻转

import java.util.ArrayList;
import java.util.Collections;
public class Solution {public ArrayList printListFromTailToHead(ListNode listNode) {ArrayList list &＃61; new ArrayList();while(listNode !&＃61; null){list.add(listNode.val);listNode &＃61; listNode.next;}Collections.reverse(list);//使用Collections的reverse方法&＃xff0c;直接将list反转return list;}
}

2.想到栈的特性先入后出&＃xff0c;完成逆序

import java.util.ArrayList;
import java.util.Stack;
public class Solution {public ArrayList printListFromTailToHead(ListNode listNode) {Stack stack&＃61;new Stack();while(listNode!&＃61;null){stack.push(listNode.val);listNode&＃61;listNode.next; }ArrayList list&＃61;new ArrayList();while(!stack.isEmpty()){list.add(stack.pop());}return list;}
}


3.递归实现 &＃xff08;递归的本质还是使用了堆栈结构&＃xff09;


import java.util.ArrayList;
import java.util.Stack;
public class Solution {public ArrayList printListFromTailToHead(ListNode listNode) {ArrayList list&＃61;new ArrayList();ListNode pNode&＃61;listNode;if(pNode!&＃61;null){if(pNode.next!&＃61;null){list&＃61;printListFromTailToHead(pNode.next);}list.add(pNode.val);}return list;}
}

【总结】

1.链表基础知识

• 新建

LinkedList lList &＃61; new LinkedList();


• 遍历

while(listNode!&＃61;null){listNode&＃61;listNode.next; }


2.堆栈基本操作

• 新建

Stack stack&＃61;new Stack();


• 出栈

while(!stack.isEmpty())
{x &＃61; stack.pop();
}


• 入栈

stack.push(val);