面试题5:从尾到头打印链表

三种方法:

1、借用栈倒序输出链表
    因为栈是先进后出,把链表中的元素存进栈中,链表前面的元素在栈底,后面的元素在栈顶,链表后面的元素先出栈

2、先翻转链表,再按顺序打印(主要是想自己实现单链表的翻转,这种实现方式破坏了链表的结构,当然再翻转一下就还原了)
     翻转链表的步骤:
     (1)将当前节点的next节点指向他以前的前一个节点
     (2)当前节点下移一位
     (3)如果是最后一个节点,就把它的next节点指向它以前的前一个节点,并推出循环

3、用递归实现
     正如那位哥们所说,递归就是一个进栈出栈的过程,链表前面的元素先进栈,在栈底,后面的元素后进栈,在栈顶,先出栈,哈哈。。。

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

 

package shuzu;

import java.util.Stack;  

public class PrintListReversingly {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Node n1 = new Node();
        Node n2 = new Node();
        Node n3 = new Node();
        n1.key = 1;
        n1.next = n2;
        n2.key = 2;
        n2.next = n3;        
        n3.key = 3;
        n3.next = null;
        
        Node head = n1;
        printListRecursively(head);
        printListIteratively(head);
    }
    /**
     * 递归的方式
     * @param n
     */
    public static void printListRecursively(Node n){
        if(null != n){
            printListRecursively(n.next);
            System.out.println(n.key);
        }
    }
    
    /**
     * 入栈、弹栈的方式
     * @param n
     */
    public static void printListIteratively(Node n){
        Stack<Node> s_node = new Stack<Node>();
        //入栈
        while (n != null) {
            s_node.push(n);
            n = n.next;
        }
        //弹栈、打印
        while (!s_node.empty()) {
            System.out.println(s_node.pop().key);
        }
    }
}

class Node
{
    int key;
    Node next;
}

 

输出结果:

3
2
1
3
2
1

 

;