Fork me on GitHub

从尾到头打印链表

发表于 | 分类于 
这是崔斯特的第一百一十二篇原创文章

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

从尾到头打印链表

题目描述

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

思路

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

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

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

解法

解法一【推荐】

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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));
    }
}

解法三

通过遍历实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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);
    }
}

栈

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
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源码中是这样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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慢。