| 题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。 链表结点定义如下： Struct ListNode{ int m_nKey; ListNode* m_pNext; }; |
我们可以用栈来实现“后进先出”的顺序。每经过一个结点的时候，把该结点防到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
void PrintListReversingly_Iteratively(ListNode* pHead){ std::stack node; ListNode* pNode = pHead; while(pNode != null){ nodes.push(pNode); pNode = pNode->m_pNext;} while(!nodes.empty()){ pNode = nodes.top(); printf("%d\t",pNode->m_nValue); nodes.pop(); }} 我们也可以用递归来实现反过来输出链表，我们每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了。
void PrintListReversingly_Recursively(ListNode* pHead){ if(pHead != null){ if(pHead->m_pNext != null){ PrintListReversingly_Recursively(pHead->m_pNext); } printf("%d\t",pHead->m_nValue); } } java精简版：
Node类：
package com.yyq;/** * Created by Administrator on 2015/9/8. */public class Node { String value; Node next; public Node(String value){ this.value = value; } public String getValue() { return value; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } public void setValue(String value) { this.value = value; }}; 处理类：
package com.yyq;import java.util.Stack;/** * Created by Administrator on 2015/9/8. */public class PrintLinkReversingly { public static void main(String[] args) { Node a = new Node("A"); Node b = new Node("B"); Node c = new Node("C"); Node d = new Node("D"); Node e = new Node("E"); Node f = new Node("F"); Node g = new Node("G"); a.next = b; b.next = c; c.next = d; d.next = e; e.next = f; f.next = g; printTailToStartRec(a); printTailToStartStack(a); } public static void printTailToStartRec(Node start) { if (start == null ) return; if (start.next!= null) { printTailToStartRec(start.next); } System.out.println(start.value); } private static void printTailToStartStack(Node node) { if (node == null) { System.out.println("list is null"); return; } Stack stack = new Stack (); while (node != null) { stack.push(node); node = node.next; } while (!stack.isEmpty()) { System.out.println(stack.pop().value); } }} 输出结果：
| F E D C B A G F E D C B A Process finished with exit code 0 |
java版本：
链表接口定义：
package com.yyq;/** * Created by Administrator on 2015/9/4. */public interface Link { //向链表增加数据 void add(Object data); //可以增加一组对象 void add(Object data[]); //在链表中删除数据 void delete(Object data); //判断数据是否存在 boolean exists(Object data); //取得全部的保存对象 Object[] getAll(); //根据保存的位置取出指定对象 Object get(int index); //求出链表的长度 int length();}
链表类定义：
package com.yyq;/** * Created by Administrator on 2015/9/4. */public class LinkImpl implements Link { class Node { private Object data; private Node next; public Node(Object data) { this.data = data; } public void addNode(Node newNode) { if (this.next == null) { this.next = newNode; } else { this.next.addNode(newNode); } } public void deleteNode(Node previous, Object data) { if (this.data.equals(data)) { previous.next = this.next; } else { if (this.next != null) { this.next.deleteNode(this, data); } } } public void getAll() { retdata[foot++] = this.data; //取出当前节点中的数据 if (this.next != null) { this.next.getAll(); } } }; private int foot = 0; private Node root; //根节点 private int len; private Object retdata[];//接收全部的返回值数据 //向链表增加数据 @Override public void add(Object data) { if (data != null) { len++; //保存个数 Node newNode = new Node(data); if (this.root == null) { this.root = newNode; } else { this.root.addNode(newNode); } } } //可以增加一组对象 @Override public void add(Object data[]) { for(int x = 0; x < data.length; x++){ this.add(data[x]); } } //在链表中删除数据 @Override public void delete(Object data) { if(this.exists(data)){ //如果存在，则执行删除 if(this.root.equals(data)){ this.root = this.root.next; }else { this.root.next.deleteNode(this.root,data); } } } //判断数据是否存在 @Override public boolean exists(Object data) { if(data == null){ return false; } if(this.root == null){ return false; } Object d[] = this.getAll();//取得全部的数据 boolean flag = false; for(int x = 0; x < d.length; x++){ if(data.equals(d[x])){ flag = true; break; } } return flag; } //取得全部的保存对象 @Override public Object[] getAll() { this.foot = 0; if(this.len != 0){ this.retdata = new Object[this.len];//根据大小开辟数组 this.root.getAll(); return this.retdata; }else{ return null; } } //根据保存的位置取出指定对象 @Override public Object get(int index) { Object d[] = this.getAll(); if(index < d.length){ return d[index]; }else{ return null; } } //求出链表的长度 @Override public int length() { return this.len; }} 链表使用举例：
package com.yyq;/** * Created by Administrator on 2015/9/4. */public class PrintListReversingly { public static void main(String[] args) { Link link = new LinkImpl(); link.add("A"); link.add("B"); link.add("C"); link.add(new String[]{"X","Y"}); Object obj[] = link.getAll(); for(Object o : obj){ System.out.println(o); } System.out.println(obj.length); System.out.println(link.exists(null)); System.out.println(link.get(3)); link.delete("X"); obj = link.getAll(); for(Object o : obj){ System.out.println(o); } System.out.println(obj.length); //注意这里还是原来obj开辟时的长度 }} 从尾到头打印链表：
package com.yyq;import java.util.Stack;/** * Created by Administrator on 2015/9/4. */public class PrintListReversingly { public static void main(String[] args) { Link link = new LinkImpl(); link.add("A"); link.add("B"); link.add("C"); link.add(new String[]{"D","E","F","G"}); Object obj[] = link.getAll(); for(Object o : obj){ System.out.println(o); } int len = obj.length; System.out.println("============"); for(int i = len-1; i >= 0; i--){ System.out.println(obj[i]); } }}