【题6 从尾到头打印链表】

【题6 从尾到头打印链表】
【题目】
输入一个链表的头节点，从头到尾反过来打印出每个结点的值。
先问：
是否允许修改输入的数据？
解决方案一：栈
首先遍历链表的节点后打印，典型的“后进先出”，可以使用栈来实现这种顺序。

• 遍历时候，每个结点放入栈中。
• 遍历完整链表后，从栈顶开始逐个输出结点的值

解决方案二：递归
栈的本质就是递归，直接使用递归的方式，打印一个节点的时候先打印它后面的节点，再打印该节点自身，实现反向打印
解决方案三：ArratList
遍历链表，把链表中的元素复制到ArrayList中，然后逆序打印ArrayList中的元素，由于ArrayList底层使用数组实现，所以用数组也是同样的原理
解决方案四：指针反转
前三种解决方案本身属于在打印链表的时候不修改链表本身结构，在允许修改链表结构的情况下可以把链表中的节点指针反转过来，改变链表方向，然后重新遍历打印改变方向后的链表。

实现

package ti5to2;

import java.util.ArrayList;
import java.util.Stack;

class ListNode{
	int val;
	ListNode next = null;
	
	public ListNode(){
	}
	public ListNode(int value){
		this.val = value;
	}
}
public class No5PrintListFromTailToHead {
	public static void main (String[] args){
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(2);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		ListNode node5 = null;
		ListNode node6 = new ListNode(6);
		ListNode node7 = new ListNode();
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		printListFromTailToHead(node1);
		printListFromTailToHead(node5);
		printListFromTailToHead(node6);
		printListFromTailToHead(node7);
		//使用栈实现逆序打印链表
		printListFromTailToHeadByStack(node1);
		//使用递归实现逆序打印链表
		printListFromTailToHead(node1);
		//使用递归反转实现逆序打印
		printListFromTailToHeadByReverseList(node1);
		//使用ArrayList逆序打印链表
		printListFromTailToHeadByArrayList(node1);
	}
	/*
	 * 方案1：通过使用栈结构，遍历链表，把先遍历的节点的值推入栈中，遍历结束通过弹出栈内元素实现逆序打印
	 */
	public static void printListFromTailToHeadByStack(ListNode node){
		Stack<Integer> stack = new Stack<Integer>();
		while(node != null){
			stack.push(node.val);
			node = node.next;
		}
		while(!stack.isEmpty()){
			System.out.println(stack.pop()+",");
		}
	}
	/*
	 * 2.递归法逆序打印链表
	 */
	public static void printListFromTailToHead(ListNode node){
		if(node != null){
			if(node.next != null){
				printListFromTailToHead(node.next);
			}
			System.out.println(node.val+",");
		}
		else{
			System.out.println("输入的链表为空");
		}
	}
	/*
	 * 3.使用ArrayList逆序打印链表
	 */
	public static void printListFromTailToHeadByReverseList(ListNode node){
		if(node == null){
			System.out.println("输入链表为null");
		}
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		//解析：Stack<NestedInteger> stack = new Stack<NestedInteger>();
		//<>代表泛型，Stack<NestedInteger>代表该Stack中只能放入NestedInteger类或者其子类的实例。
		while(node != null){
			arrayList.add(node.val);
			node = node.next;
		}
		for(int i = arrayList.size()-1;i >= 0;i--){
			System.out.println(arrayList.get(i)+",");
		}
	}
	/*
	 * 4.递归反转链表后遍历打印
	 */
	public static void printListFromTailToHeadByArrayList(ListNode node){
		ListNode reversedNode = reverse(node);
		while(reversedNode != null){
			System.out.println(reversedNode.val+",");
			reversedNode = reversedNode.next;
		}
	}
	private static ListNode reverse(ListNode head){
		if(head.next == null){
			return head;
		}
		
		ListNode reversedListNode = reverse(head.next);
		head.next.next = head;
		head.next = null;
		return reversedListNode;
	}

}

输出结果

4,
3,
2,
1,
输入的链表为空
6,
0,
4,
3,
2,
1,
4,
3,
2,
1,
4,
3,
2,
1,
4,
3,
2,
1,

注
1.结点4 5 6 7

2.方法4 指针反转

3.单链表反转
如何把一个单链表进行反转？
方法1：
将单链表储存为数组，然后按照数组的索引逆序进行反转。浪费空间
方法2：
使用3个指针遍历单链表，逐个链接点进行反转。
使用p和q两个指针配合工作，使得两个节点间的指向反向，同时用r记录剩下的链表。

p = head;
q = head->next;

head->next = NULL;

现在进入循环体，这是第一次循环。

r = q->next;
q->next = p;

p = q;
q =r;

第二次循环。

r = q->next

q->next = p; 

p = q;

q = r

。。。。。。

方法3：
从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，最后将第一个节点挪到新表的表尾。

方法是：对于一条链表，从第2个节点到第N个节点，依次逐节点插入到第1个节点(head节点)之后，(N-1)次这样的操作结束之后将第1个节点挪到新表的表尾即可。

方法4: 递归
(相信我们都熟悉的一点是，对于树的大部分问题，基本可以考虑用递归来解决。但是我们不太熟悉的一点是，对于单链表的一些问题，也可以使用递归。可以认为单链表是一颗永远只有左(右)子树的树，因此可以考虑用递归来解决。或者说，因为单链表本身的结构也有自相似的特点，所以可以考虑用递归来解决)
现在需要把A->B->C->D进行反转，
可以先假设B->C->D已经反转好，已经成为了D->C->B,那么接下来要做的事情就是将D->C->B看成一个整体，让这个整体的next指向A，所以问题转化了反转B->C->D。那么，
可以先假设C->D已经反转好，已经成为了D->C,那么接下来要做的事情就是将D->C看成一个整体，让这个整体的next指向B，所以问题转化了反转C->D。那么，
可以先假设D(其实是D->NULL)已经反转好，已经成为了D(其实是head->D),那么接下来要做的事情就是将D(其实是head->D)看成一个整体，让这个整体的next指向C，所以问题转化了反转D。

单向链表经常被设计成面试题
面试题6：从头到尾打印链表
面试题18：删除链表的节点
面试题22：链表中倒数第k个节点
面试题24：反转链表
面试题25：合并两个排序的链表
面试题52：两个链表的第一个公共节点
等

参考
1.《剑指offer》
2.https://www.cnblogs.com/gl-developer/p/6438311.html
3.https://www.weiweiblog.cn/printlistfromtailtohead/
4.https://www.cnblogs.com/mafeng/p/7149980.html