By

文章目录
  1. 1. 问题
  2. 2. 解题
    1. 2.1. 代码

问题

如何将一个链表进行逆序输出，比如1->2->3->4的链表输出为4321

解题

  1. 最方便可能就是先讲原生链表翻转，再按翻转的输出，这样会破坏原有链表的结构
  2. 第二种就是先遍历存放到一个数组或者栈中，然后从后往前输出即可，就需要额外的O(n)空间。

这两种方法都是需要额外的复杂度或者空间，网络行流传更好的方法就是使用递归-_-! 神方法啊，递归一次即可。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 使用递归 不消耗其他的空间
 * @param link
 */
public static void printTail2Head(Link link)
{
	if(link!=null && link.next!=null)
		printTail2Head(link.next);
	System.out.println(link.data);
}

static class Link{
	public int data;
	public Link next;
	public Link(int data)
	{
		this.data=data;
	}
}

这种方法固然好，但是注意，如果链表的长度很长，也许会给stackOverflowException的异常。

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权

文章目录
  1. 1. 问题
  2. 2. 解题
    1. 2.1. 代码