首页 > 试题广场 > 从尾到头打印链表
[编程题]从尾到头打印链表
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。

231个回答

添加回答
推荐
方法一:链表从尾到头输出,利用递归实现,不使用库函数直接printf输出的时候用递归比较好
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> value;
        if(head != NULL)
        {
            value.insert(value.begin(),head->val);
            if(head->next != NULL)
            {
                vector<int> tempVec = printListFromTailToHead(head->next);
                if(tempVec.size()>0)
                value.insert(value.begin(),tempVec.begin(),tempVec.end());  
            }         
            
        }
        return value;
    }
};
方法二:用库函数,每次扫描一个节点,将该结点数据存入vector中,如果该节点有下一节点,将下一节点数据直接插入vector最前面,直至遍历完,或者直接加在最后,最后调用reverse
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(struct ListNode* head) {
        vector<int> value;
        if(head != NULL)
        {
            value.insert(value.begin(),head->val);
            while(head->next != NULL)
            {
                value.insert(value.begin(),head->next->val);
                head = head->next;
            }         
            
        }
        return value;
    }
};

编辑于 2015-06-18 16:53:34 回复(62)
可以使用栈的先入后出特性,不过需要额外引入java.util.Stack;在不使用栈的情况下,我的解决方法是先反转链表再存入到ArrayList。
发表于 2019-05-16 10:16:56 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    if (listNode == null) {
        return list;
    }
    list.add(listNode.val);
    while ((listNode = listNode.next) != null) {
        list.add(listNode.val);
    }
    for (int i = 0; i < list.size() / 2 ; i++) {
        Collections.swap(list, i , list.size() - i - 1);
    }
     return list;
}
第一想法是这样的😂

编辑于 2019-05-13 22:42:26 回复(0)
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
* 递归实现
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        
        ArrayList<Integer> arr = new ArrayList<>();
        
        if(listNode!=null){
            arr.addAll(printListFromTailToHead(listNode.next));
        
            arr.add(listNode.val);
        }
        return arr;
        
        
        
        
        
    }
}

编辑于 2019-05-11 10:31:12 回复(0)
提取关键字:从尾至首返回值,而链表插入是类似队列的,此时可以利用栈的进栈和出栈,把出栈的值加入链表就行了
发表于 2019-05-06 10:06:28 回复(0)
我最开始写的是:

    public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        ArrayList<Integer> tempList = new ArrayList<>();

        // !!! 错误在这里,当入参为null就会报空指针
        while (listNode.next != null) {
            tempList.add(listNode.val);
            listNode = listNode.next;
        }
        tempList.add(listNode.val);

        for (int i = tempList.size(); i > 0; i--) {
            arrayList.add(tempList.get(i - 1));
        }

        return arrayList;
    }

第一次玩在线编程,哈哈,没注意各种测试用例,在此立下flag不再犯,哈哈哈。

编辑于 2019-05-01 22:19:08 回复(0)
这滑稽的代码长度,居然通过了!
时间复杂度O(N),空间复杂度O(1)(如果不考虑递归栈的话)
public class Solution {//Java Ver.
  public ArrayList<Integer> printListFromTailToHead(ListNode listNode, List... list) {
    if(list.length==0) list=new ArrayList[]{new ArrayList()};
    if(listNode==null) return (ArrayList<Integer>)list[0];
    printListFromTailToHead(listNode.next,list[0]);//先将节点右边的部分插进去
    list[0].add(listNode.val);//反正目前的节点是插在最后了
    return (ArrayList<Integer>)list[0];
  }
}

编辑于 2019-04-28 06:38:23 回复(0)
/** *    public class ListNode { *        int val; *        ListNode next = null; * *        ListNode(int val) { *            this.val = val; *        } *    } * */ import java.util.ArrayList; import java.util.Stack; public class Solution {     public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {         ArrayList<Integer> result = new ArrayList<>();         if (listNode == null) {             return result;         }         Stack<ListNode> stack = new Stack();         while (listNode != null) {             stack.push(listNode);             listNode = listNode.next;         }         while (!stack.empty()) {             result.add(stack.pop().val);         }         return result;     } }

编辑于 2019-04-23 10:18:50 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
     ArrayList<Integer> list=new ArrayList<Integer>();
     int[] array=new int[1000];
     int i=0;
     if(listNode==null) return list;
     array[i++]=listNode.val;
     while(listNode!=null) {   //
          listNode=listNode.next;
          if(listNode!=null)
             array[i++]=listNode.val;
         }
     for(;i>0;) {
           list.add(array[--i]);
     }
     return list;
    }
发表于 2019-04-20 14:25:15 回复(1)
import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList();
        while(listNode != null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(list);
        return list;   
    }
}
发表于 2019-04-17 16:57:34 回复(0)
将链表反转后再进行输出.
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
  ListNode cur = listNode;
  ListNode pre = null;
  while (true) {
    if (cur == null) {
      ArrayList<Integer> arrayList = new ArrayList();
      while (pre != null) {
        arrayList.add(pre.val);
        pre = pre.next;
      }
      return arrayList;
    }
    ListNode tmp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = tmp;
  }
}


编辑于 2019-04-17 15:33:19 回复(0)

import java.util.*;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> lists=new ArrayList<Integer>();
        if(listNode==null){
            return lists; 
        }
        //临时用来代替listNode
        ListNode listNode1=listNode
        //遍历下一个(如果listNode1的下一个不等于null;
        while(null!=(listNode1=listNode1.next)){
                //总是放在lists的第一个
              lists.add(0,listNode1.val);     
        }
       //添加第一个Node到lists的最后。
        lists.add(listNode.val);
        return lists;
    }
}
时间复杂度为1n,嘻嘻嘻,怎么说。
发表于 2019-04-11 22:02:10 回复(0)
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        while(listNode!=null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
       Collections.reverse(list);
        return list;
    }
}
发表于 2019-04-09 23:17:11 回复(0)

//先将元素push到栈中,然后将元素依次弹出添加到list集合中

import java.util.ArrayList; import java.util.Stack; public class Solution { public ArrayList printListFromTailToHead(ListNode listNode) { ArrayList list = new ArrayList(); Stack stack = new Stack(); if(listNode == null){
        return list;
    }
    while(listNode != null){
        stack.push(listNode.val);

        listNode = listNode.next;
    }

    while(stack.size()>0){
        list.add(stack.pop());
    }

    return list;
}

}

编辑于 2019-04-07 14:16:27 回复(0)
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        ListNode temp = listNode;
        while ( temp != null ) {
            list.add( temp.val );
            temp = temp.next;
        }
        for ( int i = list.size()-1; i>=0; i-- ) {
            result.add( list.get(i) );
        }
        return result;
    }
}

发表于 2019-04-05 00:26:43 回复(0)
/*
*递归反转链表
*/
import java.util.ArrayList;

public class Solution{
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> lists = new ArrayList<>();
        ListNode list = new ListNode(0);
        list.next = reverseList(listNode);
        while (list.next != null) {

            lists.add(list.next.val);
            list = list.next;
        }
        return lists;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode cur = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }
}

发表于 2019-04-04 21:50:34 回复(0)
//方案一:利用栈,入栈出栈
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
         Stack<Integer> a=new Stack<Integer>();
        while (listNode!=null){
            a.push(listNode.val);
            listNode=listNode.next;
        }
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        while (!a.empty()){
            arrayList.add(a.pop());
        }
        return arrayList;
        
    }
    
//方案二:头插法
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ListNode temp=ReverseList(listNode);
    ArrayList<Integer> list=new ArrayList(); while(temp!=null){
        list.add(temp.val);
        temp=temp.next;
    } return list;
}
ListNode ReverseList(ListNode listNode){ if(listNode==null||listNode.next==null)  return listNode;
    ListNode prev=null;
    ListNode cur=listNode; while(cur!=null){
        ListNode temp=cur;//设置临时结点
        cur=cur.next;//设置好头结点
        temp.next=prev;//插入头部
        prev=temp ;//指针前移
    } return prev;
}


//方案三:使用Collections的reverse方法,直接将list反转
import java.util.ArrayList;
import java.util.Stack;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arrayList=new ArrayList<Integer>();
        while (listNode!=null){
            arrayList.add(listNode.val);
            listNode=listNode.next;
        }
        Collections.reverse(arrayList);
        return arrayList;
        
    }          
}




编辑于 2019-04-02 14:50:31 回复(0)
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();  
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        if (list != null && list.size() > 1) {
            Collections.reverse(list);
        }
        return list;
        
    }
}
发表于 2019-04-01 17:57:38 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> result = new ArrayList<>();  if(listNode == null){  return result;    }else {
        result = printListFromTailToHead(listNode.next);
      result.add(listNode.val);
      return result; }
}

java 递归简洁版
发表于 2019-03-30 11:28:18 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> a = new ArrayList<Integer>();
            while(listNode!=null){
                a.add(0,listNode.val);
                listNode = listNode.next;
            }
        return a;
    }
}

//不过貌似这个方法复杂度比较高?
发表于 2019-03-29 17:40:17 回复(0)
方法一:利用栈后进先出的思想,将链表的顺序逆序
/**
 *    public class ListNode {
 *        int val;
 *        ListNode next = null;
 *
 *        ListNode(int val) {
 *            this.val = val;
 *        }
 *    }
 *
 */
 import java.util.ArrayList;
 import java.util.Stack;
 public class Solution {
 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
 //定义一个栈用于存放新给的数据
 Stack<Integer> stack = new Stack<Integer>();
 //定义一个数组列表用于存放返回数据
 ArrayList<Integer> list = new ArrayList<Integer>();
 //如果链表节点不为空,则把数据依次压入堆栈中
 while(listNode != null){
 stack.push(listNode.val);
 listNode = listNode.next;
 }
 //如果堆栈不为空,则把数据依次弹出并添加到列表中
 while(!stack.isEmpty()){
 list.add(stack.pop());
 }
 //返回逆序后的链表值
 return list;
 }
 }

方法二:利用递归调用的思想,对每个节点依次进行递归
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    //定义一个数组列表,用于存放逆序后的数据
    ArrayList<Integer> arrayList=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        /**
        *  如果链表节点不为空,对下一个节点调用当前方法(即递归调用)
        *  递归到最后一个节点的下一个节点,此时返回到最后一个节点
        *  将最后一个节点的值添加到列表中,依次返回上一层调用
        */
        if(listNode!=null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        //返回逆序后的数据
        return arrayList;
    }
}

编辑于 2019-03-29 10:49:44 回复(0)