2

从尾到头打印链表

 2 years ago
source link: https://zhangslob.github.io/2020/01/05/%E4%BB%8E%E5%B0%BE%E5%88%B0%E5%A4%B4%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client 
这是崔斯特的第一百一十二篇原创文章

努力、奋斗 (๑• . •๑)

从尾到头打印链表

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

链表从头到尾输出会比较简单，于是我们很自然的想到把链表中链接节点的指正翻转过来，改变链表的方向，然后就可以从头到尾的输出了。但是该方法会修改原来链表的结构，这应该不是一个好的选择。

在面试中，如果我们打算修改输入的数据，最好先问面试官是否允许修改。

这道题肯定需要遍历链表的，但是遍历肯定是顺序，可是最终需要的是从尾到头，这就是典型的”先进先出“，可以使用栈实现。遍历该链表时，没经过一个节点，便把该节点放入栈中。遍历结束之后，再从栈顶输出所有值。

解法一【推荐】

遍历链表，每个链表结点值 push 进栈，最后将栈中元素依次 pop 到 list 中。

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<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
while (!stack.isEmpty()) {
res.add(stack.pop());
return res;
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
listNode.next = new ListNode(2);
listNode.next.next = new ListNode(3);
listNode.next.next.next = new ListNode(4);
listNode.next.next.next.next = new ListNode(5);
System.out.println(new Solution().printListFromTailToHead(listNode));

面试官看到使用了栈，会不会手动让你完成栈的实现呢。下面有栈的实现。

解法二【不推荐】

利用递归方式：

  1. 若不是链表尾结点，继续递归；
  2. 若是，添加到 list 中。

这种方式不推荐，当递归层数过多时，容易发生 Stack Overflow。

public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> res = new ArrayList<>();
if (listNode == null) {
return res;
addElement(listNode, res);
return res;
private void addElement(ListNode listNode, ArrayList<Integer> res) {
if (listNode.next != null) {
addElement(listNode.next, res);
res.add(listNode.val);
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
listNode.next = new ListNode(2);
listNode.next.next = new ListNode(3);
listNode.next.next.next = new ListNode(4);
listNode.next.next.next.next = new ListNode(5);
System.out.println(new Solution().printListFromTailToHead(listNode));

通过遍历实现

public class Solution {
public void printListFromTailToHead(ListNode listNode) {
ListNode pre = null;
ListNode next = null;
while (listNode != null) {
next = listNode.next;
listNode.next = pre;
pre = listNode;
listNode = next;
while (pre != null) {
System.out.println(pre.val);
pre = pre.next;
public static void main(String[] args) {
ListNode listNode = new ListNode(1);
listNode.next = new ListNode(2);
listNode.next.next = new ListNode(3);
listNode.next.next.next = new ListNode(4);
listNode.next.next.next.next = new ListNode(5);
new Solution().printListFromTailToHead(listNode);

研究了下源码，简单实现了下：

import java.util.Arrays;
import java.util.EmptyStackException;
* @author zhujian on 2020/1/5.
public class Stack<E> {
* 元素数量
private int elementCount;
* 储存数据的数组
private Object[] elementData;
* 自定义最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
* 构造方法，默认大小为10
public Stack() {
this(10);
public Stack(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
this.elementData = new Object[initialCapacity];
* @param item
* @return
public E push(E item) {
if (elementCount + 1 - elementData.length > 0) {
grow(elementCount + 1);
elementData[elementCount++] = item;
return item;
* @return
public E pop() {
E item;
item = peek();
removeElementAt(elementCount - 1);
return item;
public boolean isEmpty() {
return elementCount == 0;
* 取出数组最右边元素
* @return
public E peek() {
int len = elementCount;
if (len == 0) {
throw new EmptyStackException();
return (E) elementData[len - 1];
* 移除数组最右边元素
* @param index
public void removeElementAt(int index) {
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
} else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
elementCount--;
elementData[elementCount] = null;
* 数组长度不够时，为数组扩大空间
* @param minCapacity
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity * 2;
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
if (newCapacity > MAX_ARRAY_SIZE) {
if (minCapacity < 0) {
throw new OutOfMemoryError();
newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
elementData = Arrays.copyOf(elementData, newCapacity);

JDK源码中是这样的

package java.util;
public
class Stack<E> extends Vector<E> {
public Stack() {
public E push(E item) {
addElement(item);
return item;
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
public boolean empty() {
return size() == 0;
public synchronized int search(Object o) {
int i = lastIndexOf(o);
if (i >= 0) {
return size() - i;
return -1;
private static final long serialVersionUID = 1224463164541339165L;

细节满满，想要看更多实现就需要去看Vector的源码了。Vector日常使用的太少了，是线程安全的，但实现同步需要很高的花费，因此访问比ArrayList慢。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK