从尾到头打印链表

题目描述

给定一个链表，从尾部到头部打印输出链表的值。

栈方式

很自然，想到的第一个方法就是后进先出，那就是直接可用栈来模拟
当然，因为题目要求使用链表，所以首先可确定结点结构，如下

public class Node<T extends Object> {

	T data;
	 public Node next;
	
	public Node(Node next){
		this.next=next;
	}
	public Node(T data){
		this.data=data;
	}
	
	public T getData(){
		return this.data;
	}

接下来就是栈方式

class LinkNode{
	 
	 void Resver(Stack<Node> stack){
		 while(!stack.isEmpty()){
		 System.out.println((stack.pop()).data);
		 }
	 }

	 public static void main(String args[]){
		Node A=new Node(1);
		Node B=new Node(2);
		Node C=new Node(3);
	    A.next=B;
	    B.next=C;
	    C.next=null;
	    LinkNode link=new LinkNode();
	    Stack stack=new Stack<>();
	    stack.push(A);
	    stack.push(B);
	    stack.push(C);
	    link.Resver(stack);
		
	}

会发现用利用栈的特点可以很快的非递归实现此功能

递归方式

另一种想法就是利用递归树的特点，也就是说如果你有后继结点，就递归寻找后继结点，直到找到最后一个后继结点，然后打印结点值，就是想象成一棵斜数，然后后续遍历

Node TraverserHeadToTail(Node node){
	 if(node!=null){
		if(node.next!=null){
			 TraverserHeadToTail(node.next);
		 }
		System.out.println(node.data);
	 return node;
	 }
	 else {
		 System.out.println("null");
		 return null;
	 }
 }

 public static void main(String args[]){
	Node A=new Node(1);
	Node B=new Node(2);
	Node C=new Node(3);
    A.next=B;
    B.next=C;
    C.next=null;
    LinkNode link=new LinkNode();
    link.TraverserHeadToTail(A);	
}

可以发现递归的方式如此简便，注意这里的node返回的是根结点，因为它是后续遍历的最后一个结点啊

顺序表方式

能不能把链表转换成顺序表了，大体思路是这样的，对链表做三次遍历，第一次遍历确定链表的长度，第二次遍历将每个结点的值按照结点顺序放到一个缓存中，第三次遍历，对该缓存遍历，然后将到放到另一个缓存数组中，不过是将前一个缓存按照倒序放到该数组中，最后将该倒序缓存放到集合中就可以了，代码如下

ArrayList<Integer> ChangeToList(Node node){
		 int len = 0,i=0;
		 Node temp=node;
		 while(node!=null){
			 ++len;
			 node=node.next;
		 }
		 Integer[] nodes=new Integer[len];
		 while(temp!=null)
		 {
			 nodes[i++]=(Integer) temp.data;
			 temp=temp.next;
		 }
		
		 Integer[] nodesTemp=new Integer[len];
		 for(int j=0;j<nodes.length;j++)
			 nodesTemp[len-j-1]=nodes[j];
		 ArrayList<Integer> list=new ArrayList<>();
		 for(int k=0;k<nodes.length;k++)
			 list.add(k, nodesTemp[k]);
		 return list;	 
	 }


	 public static void main(String args[]){
		Node A=new Node(1);
		Node B=new Node(2);
		Node C=new Node(3);
	    A.next=B;
	    B.next=C;
	    C.next=null;
	    LinkNode link=new LinkNode();
	    List<Integer> list=link.ChangeToList(A);
	    for(Integer val:list)
	    	System.out.println(val);
		
	}