题目描述:
给定一个链表,从尾部到头部打印输出链表结点的值。看到这个题目我的基本思路是:首先遍历一遍链表,统计出结点的个数,然后进行第二次遍历把每次访问的结点的值方到一个临时数组中,遍历结束之后,该临时数组中的值与正向遍历链表的值的顺序是一样的。那么在第三次遍历的时候,把上面的临时数组拷贝到另外一个临时数组中,只不过这次拷贝是从最后一个位置的值开始拷贝的,这样第三次遍历结束之后,第二个临时数组中的值的顺序就是从尾到头遍历链表的值的顺序了。最后一次遍历就是把第二个临时数组转化为一个ArrayList对象,并返回。
已知如下条件:
public class ListNode{
int val;
ListNode next = null;
ListNode(int val){
this.val = val;
}
}
下面是我未参照书上的解法自己实现的,时间复杂度也是O(n)。下面是在牛客OJ提交成功的代码:
package com.rhwayfun.offer;
import java.util.ArrayList;
import java.util.List;
/**
* 题目描述:从尾到头打印链表
* @author Administrator
*
*/
public class PrintLinkListFromTailToFront {
static class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
int len = 0, i = 0;
ListNode temp = listNode;
while (listNode!= null) {
++len;
listNode = listNode.next;
}
Integer[] nodes = new Integer[len];
while (temp!= null) {
nodes[i++] = temp.val;
temp = temp.next;
}
Integer[] nodes2 = new Integer[len];
for (int j = 0; j < nodes.length; j++) {
nodes2[len - 1 -j] = nodes[j];
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int j = 0;j<nodes.length;j++){
list.add(j, nodes2[j]);
}
return list;
}
public static void main(String[] args) {
ListNode root = new ListNode(1);
ListNode node1 = new ListNode(2);
ListNode node2 = new ListNode(3);
ListNode node3 = new ListNode(4);
root.next = node1;
node1.next = node2;
node2.next = node3;
List<Integer> list = new PrintLinkListFromTailToFront().printListFromTailToHead(root);
for (Integer integer : list) {
System.out.print(integer + "\t");
}
}
}