| 题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。 链表结点定义如下： Struct ListNode{ int m_nKey; ListNode* m_pNext; }; |
我们可以用栈来实现“后进先出”的顺序。每经过一个结点的时候，把该结点防到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
void PrintListReversingly_Iteratively(ListNode* pHead){std::stack<ListNode*> 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<Node> stack = new Stack<Node>();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[];//接收全部的返回值数据//向链表增加数据 @Overridepublic 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);}}}//可以增加一组对象 @Overridepublic void add(Object data[]) {for(int x = 0; x < data.length; x++){this.add(data[x]);}}//在链表中删除数据 @Overridepublic 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);}}}//判断数据是否存在 @Overridepublic 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;}//取得全部的保存对象 @Overridepublic Object[] getAll() {this.foot = 0;if(this.len != 0){this.retdata = new Object[this.len];//根据大小开辟数组this.root.getAll();return this.retdata;}else{return null;}}//根据保存的位置取出指定对象 @Overridepublic Object get(int index) {Object d[] = this.getAll();if(index < d.length){return d[index];}else{return null;}}//求出链表的长度 @Overridepublic 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]);}} }
