[名企面试知识点][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;
   }
}
添加回复
回到顶部