[数据结构与算法]面试题6：从尾到头打印链表

题目：输入一个链表的头节点，从尾到头反过来打印出每个系欸但的值。链表节点定义如下
本实现方法有头节点，头节点没有数据域

class Node{
	int value;
	Node next;
	
	public Node() {
	}
	public Node(int value) {
		this.value = value;
	}
		
	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
}

第一种方法：使用栈结构打印

// 反向遍历链表  从未到头打印
	public void PrintListReversingly_IterativeLy(){ 
		if(head==null || head.next==null){
			throw new IllegalArgumentException("头节点为空，或链表为空");
		}
		// 利用栈结构将链表节点传入先进后出实现反向打印
		Stack<Node>	stack = new Stack<Node>();
		
		// 遍历链表将 遍历到的节点装入栈中
		//设置游标节点 第一个有效节点设为开始游标节点
		Node temp=head.next;
		
		while(temp!=null){
			// 将节点装如栈中
			stack.push(temp);
			// 接着往下遍历
			temp=temp.next;
		}
		
		// 一次将栈弹出
		while(!stack.empty()){
			System.out.println(stack.pop());
		}
	}

第二种：利用递归方法从尾到头

	// 递归打印节点
	public void PrintListReversingly_Recursively(Node head){
		if(head!=null){
			if(head.next.next!=null){
				PrintListReversingly_Recursively(head.next);
			}
			System.out.println(head.next);
		}
	}

完整源代码：

package com.basic;

import java.util.Scanner;
import java.util.Stack;

public class Queue_01 {
	// 创建头节点
	private static Node head=new Node(0);
	
	public static void main(String[] args) {
		Queue_01 queue = new Queue_01();
		Scanner sc=new Scanner(System.in);
		boolean isOK=true;
		while(isOK){
			System.out.println("输入  1 添加链表节点   2反序打印链表   3递归遍历  4退出");
			char c=sc.next().charAt(0);
			switch (c) {
			case '1':
				try{
					System.out.println("请输入想要添加的节点数字");
					String i=sc.next();
					Queue_01.Node node = new Queue_01.Node(Integer.parseInt(i));
					queue.AddByOrder(node);
				}catch(Exception e){
					System.out.println(e.getMessage());
				}
				break;
			case '2':
				try{
					queue.PrintListReversingly_IterativeLy();
				}catch(Exception e){
					System.out.println(e.getMessage());
				}
				break;
			case '3':
				queue.PrintListReversingly_Recursively(head);
				break;
			case '4':
				isOK=false;
				break;
			}
		}
	}
	
	public void AddByOrder(Node newNode){
		if(newNode==null){
			throw new IllegalArgumentException("传入节点有误，添加失败");
		}
		// 设立指针游标节点
		Node temp=head;
		// 设置添加标志位
		boolean isOK=false;
		
		// 开始遍历寻找插入位置 找到插入节点的上一个节点
		while(true){
			if(temp.next==null){
				// 说明当前节点应该插入到尾部
				break;
			}else if(temp.next.value==newNode.value){
				// 说明存在重复节点 不插入
				isOK=true;
				break;
			}else if(temp.next.value > newNode.value){
				// 找到了插入的位置
				break;
			}
			// 没有找到一直往下遍历 知道末尾节点
			temp=temp.next;
		}
		
		// 利用标志位 决定是否加入节点
		if(!isOK){
			// 将游标节点的下一个节点设置为新节点的下一个节点
			newNode.next=temp.next;
			// 将游标节点的下一个节点设置为新节点
			temp.next=newNode;
		}
	}
	
	// 反向遍历链表  从未到头打印
	public void PrintListReversingly_IterativeLy(){ 
		if(head==null || head.next==null){
			throw new IllegalArgumentException("头节点为空，或链表为空");
		}
		// 利用栈结构将链表节点传入先进后出实现反向打印
		Stack<Node>	stack = new Stack<Node>();
		
		// 遍历链表将 遍历到的节点装入栈中
		//设置游标节点 第一个有效节点设为开始游标节点
		Node temp=head.next;
		
		while(temp!=null){
			// 将节点装如栈中
			stack.push(temp);
			// 接着往下遍历
			temp=temp.next;
		}
		
		// 一次将栈弹出
		while(!stack.empty()){
			System.out.println(stack.pop());
		}
	}
	
	// 递归打印节点
	public void PrintListReversingly_Recursively(Node head){
		if(head!=null){
			if(head.next.next!=null){
				PrintListReversingly_Recursively(head.next);
			}
			System.out.println(head.next);
		}
	}
	
	static	class Node{
		int value;
		Node next;
		
		public Node() {
		}

		public Node(int value) {
			this.value = value;
		}

		@Override
		public String toString() {
			return "Node [value=" + value + "]";
		}
		
	}
}

此代码思路参考剑指offer 面试题