逆向打印链表

逆向打印链表

输入一个链表的头节点,从尾到头反过来打印出每个节点的值。

练表节点定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Node {
Integer data;
Node next;
public Node(Integer data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}

通常打印是一个只读操作,我们不希望打印时修改内容。假设面试官也要求这个题目不能改变链表的结构。

接下来我们想到解决这个问题肯定要遍历链表。遍历的顺序是从头到尾,可输出的顺序却是从尾到头。也就是说,第一个遍历到的节点最后一个输出,为最后一个遍历到的节点第一个第一个输出。这就是典型的“后进先出”,我们可以用栈实现这种顺序。每经过一个节点的时候,该节点放到一个栈中。当遍历完整个链表后,再从站定开始逐个输出节点的值,此时输出的节点顺序已经返过来了。这种思路的具体实现代码如下。

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
/**
* 数组创建链表
* @param list
* @return
*/
private static Node createLinkedList(List<Integer> list) {
if (list == null || list.isEmpty()) {
return null;
}

Node firstNode = new Node(list.get(0));

Node headOfSublist = createLinkedList(list.subList(1, list.size()));
firstNode.setNext(headOfSublist);
return firstNode;
}

/**
* stack 的方式实现链表逆向打印
* @param head head
*/
private static void printListRevers(Node head) {
if (head == null) {
return;
}

Node node = head;
Stack<Integer> stack = new Stack<>();
// 把链表数据加入栈
while (node != null) {
stack.push(node.getData());
node = node.getNext();
}

while (!stack.isEmpty()) {
Integer integer = stack.pop();
System.out.println(integer);
}
}

既然想到了用栈来实现这个函数,而递归在本质上就是一个栈结构,于是又想到了用递归来实现。要实现反过来输出链表,我们每访问到一个节点的时候,先递归输出它后面的节点,再输出该节点自身,这样链表的输出结果就反过来了。

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 递归方式实现链表逆向打印
* @param head head
*/
private static void printListReversed(Node head) {
if (head == null) {
return;
}
if (head.getNext() != null) {
printListReversed(head.getNext());
}
System.out.println(head.getData());
}

上面的基于递归的代码看起来很简洁,但有一个问题:当链表非常长的时候,就会导致函数调用的层级很深,从而有可能导致函数调用栈溢出。显然用栈循环实现的代码更好一些。

------ 本文结束,欢迎阅读------
欢迎关注公众号,不定期更新