- 主页/
- [名企面试知识点][Java]从尾到头打印链表
[名企面试知识点][Java]从尾到头打印链表
发布于 2017-03-10 14:05
2335 次浏览
0 赞
来自 笔试面试
题目描述
输入一个链表,从尾到头打印链表每个节点的值。
输入描述
输入为链表的表头
输出描述
输出为需要打印的“新链表”的表头
题目分析
链表节点类
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
解法一
根据Stack的特点 后进先出(LIFO),可以先遍历链表,把值存入堆栈中。然后新建一个链表对象做为返回,再把堆栈中的值依次拿出来存入新链表中, 就实现了倒序。
运行时间:29ms 占用内存:503k
import java.util.*;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack<Integer> st = new Stack<Integer>();
while(listNode!=null){
st.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<Integer>();
while(!st.empty()){
list.add(st.pop());
}
return list;
}
}
注意Stack 申明时要确定存入数据的具体类型(Integer),否则 pop()函数返回的是Object对象,需要 强转。
解法二
直接新建一个ArrayList对象 list,遍历链表把值存入list中。再调用Collections工具类的反转函数把list反转,最后返回。
运行时间:35ms 占用内存:654k
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list= new ArrayList<Integer>();
if(listNode!=null)
{
list.add(listNode.val);
ListNode nextnode=listNode.next;
while(nextnode!=null){
list.add(nextnode.val);
nextnode=nextnode.next;
}
Collections.reverse(list);
}
return list;
}
}
这是 Collections.reverse()函数源码,性能比第一种差一点。
374 public static void More ...reverse(List<?> list) {
375 int size = list.size();
376 if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
377 for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
378 swap(list, i, j);
379 } else {
380 // instead of using a raw type here, it's possible to capture
381 // the wildcard but it will require a call to a supplementary
382 // private method
383 ListIterator fwd = list.listIterator();
384 ListIterator rev = list.listIterator(size);
385 for (int i=0, mid=list.size()>>1; i<mid; i++) {
386 Object tmp = fwd.next();
387 fwd.set(rev.previous());
388 rev.set(tmp);
389 }
390 }
391 }
解法三
新建两个ArrayList对象 list1和list2,遍历链表把值存入list1。再把list1从后到前 遍历,把值放入list2中(实现反转),返回list2;
运行时间:28ms 占用内存:629k
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list1 = new ArrayList<Integer>();
ArrayList<Integer> list2 = new ArrayList<Integer>();
while(listNode!=null){
list1.add(listNode.val);
listNode=listNode.next;
}
for(int i=list1.size()-1;i>=0;i--){
list2.add(list1.get(i));
}
return list2;
}
}
添加回复