首页 > 试题广场 > 从尾到头打印链表
[编程题]从尾到头打印链表
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
推荐
方法一:链表从尾到头输出,利用递归实现,不使用库函数直接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 回复(67)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode != null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}
发表于 2019-11-06 10:53:51 回复(0)
用个递归很方便
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> result = new ArrayList<>();
        helper(listNode, result);
        return result;
    }
    
    private void helper(ListNode listNode, ArrayList<Integer> result) {
        if (listNode == null) {
            return;
        }
        helper(listNode.next, result);
        result.add(listNode.val);
    }
}
发表于 2019-11-03 18:43:41 回复(0)
//遍历链表 将元素存入栈中
//也可以再新建一个链表采用头插法
//也可以建立两个vector 一个用来暂存,另一个反向存储、输出
//其他的方法没有想到
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
      //遍历链表 将元素存入栈中
       //也可以再新建一个量表采用头插法
        //也可以建立两个vector 一个用来暂存,另一个反向存储、输出
        vector <int> arr;
        vector <int> arr2;
        ListNode*  p=head;
        while(p!=NULL){
          arr.push_back(p->val);
            p=p->next;
        }
        for(int i=arr.size()-1;i>=0;i--){
            arr2.push_back(arr[i]);
        }
        return arr2;
    }
};
//java
/**
*    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> arrlist = new ArrayList<Integer>();
        ArrayList<Integer> ans = new ArrayList<Integer>();
        ListNode ln=listNode;
        while(ln!=null){
            arrlist.add(ln.val);
            ln=ln.next;
        }
        for(int a=arrlist.size()-1;a>=0;a--){
            ans.add(arrlist.get(a));
        }
        return ans;
    }
}



编辑于 2019-10-22 10:57:03 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> arrayList = new ArrayList<Integer>();
        if (listNode != null) {
            while (listNode != null) {
                arrayList.add(0, listNode.val);
                listNode = listNode.next;
            }
        }
        return arrayList;
    } 
java方法
发表于 2019-10-14 07:58:12 回复(0)
解题思路:
1.首先判断输入的链表对象是否为空
2.由于ArrayList是有顺的又由于要求从尾到头,所以可以另写一个递归函数用于往ArryList添加元素
3.递归函数逻辑先判断是否是链尾,否则往下递归,直到链尾才开始往ArraList添加元素,从而实现尾到头

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        if(listNode==null)return list;
        add(list,listNode);
        return list;
    }
    public void add(ArrayList<Integer> list,ListNode listNode){
        if(listNode.next!=null)
            add(list,listNode.next);
        list.add(listNode.val);
    }

编辑于 2019-10-09 22:36:49 回复(0)
import java.util.*;
public class Solution {
    // Reverse a LinkedList using stack
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        // init:
        Deque<ListNode> stack = new ArrayDeque<>();
        ArrayList<Integer> res = new ArrayList<>();
        
        // 1. Load listNode
        ListNode ptr = listNode;
        while(ptr != null){
            stack.offerFirst(ptr);
            ptr = ptr.next;
        }
        // 2. pop it out
        while(!stack.isEmpty()){
            ListNode node = stack.pollFirst();
            res.add(node.val);
        }
        return res;
    }
}

发表于 2019-10-07 12:19:34 回复(0)
遍历链表并把val依次插入arrayList数组,然后利用Collections的reverse方法把数组反转
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){
           ListNode p = listNode;
 
            while(p!=null){
                list.add(p.val);
                p = p.next;
            }          
        }
        ArrayList<Integer> a = new ArrayList<>();
     Collections.reverse(list);
        return list;
    
    }
}


发表于 2019-10-06 18:32:26 回复(0)
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> list = new ArrayList<>();
    ListNode start = listNode;
    while (start != null){
        list.add(0,start.val);
        start = start.next;
    }
    return list;
}
从尾到头,可以利用list.add(int index,Integer element),使先添加进的元素自动后移
发表于 2019-09-28 22:25:17 回复(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> list = new ArrayList<Integer>();
//利用栈的先进后出进行“反转”操作
        Stack<Integer> s = new Stack<Integer>();
        while(listNode.next!=null){
            s.push(listNode.val);
            listNode = listNode.next;
        }
        while(! s.isEmpty()){
            list.add(s.pop());
        }
        return list;
    }
}

发表于 2019-09-28 22:07:48 回复(0)
不可以使用list存储然后使用Collections。reverser翻转吗
发表于 2019-09-27 19:43:18 回复(1)
   public class ListNode {
        int val;
       ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }


import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    ArrayList<Integer> a = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ListNode temp =  listNode;
        while(temp!=null){
                a.add(temp.val);
                temp = temp.next;
        }
        Collections.reverse(a);
        return a;
    }
}
好傻的方法,主要是对api不熟,可以把 a.add(temp.val);换成 a.add(0,temp.val);
发表于 2019-09-14 13:08:51 回复(0)
先反转链表,再添加数据。
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(listNode == null)
            return list;
        ListNode current = listNode;
        ListNode newlist = null;
        ListNode temp = null;
        while (current != null){
            temp = current.next;
            current.next = newlist;
            newlist = current;
            current = temp;
        }
        while(newlist != null){
            list.add(newlist.val);
            newlist = newlist.next;
        }
        return list;
    }
}

编辑于 2019-09-20 14:20:05 回复(1)
这里我使用了Collection工具类直接对arraylist进行翻转,因此这道题只需要按照顺序遍历单链表并且将其依次录入arraylist,然后再使用Collection直接对arraylist进行翻转,然后return arraylist,问题解决。
在写下这代码的时候我犯了两个很傻的错误,一个是没有对输入参数验证是否为空,另一个是在遍历时使用了tmp.next而不是tmp作为判断条件。
/**
 *    public class ListNode {
 *        int val;
 *        ListNode next = null;
 *
 *        ListNode(int val) {
 *            this.val = val;
 *        }
 *    }
 *
 */
import java.util.ArrayList;
import java.util.Collections;

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arraylist = new ArrayList<Integer>();
        if (listNode==null){
            return arraylist;
        }
        ListNode tmp =listNode;
        while(tmp!=null){
            arraylist.add(tmp.val);
            tmp=tmp.next;
        }
        Collections.reverse(arraylist);
        return arraylist;
    }
}



编辑于 2019-09-11 15:40:04 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList();
        if(listNode != null){
            list.addAll(printListFromTailToHead(listNode.next));
            list.add(listNode.val);
        }
        return list;
    }
}

或者这样写:
import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> list = new ArrayList(); //把Arraylist写到外面
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            printListFromTailToHead(listNode.next);
            list.add(listNode.val);
        }
        return list;
    }
}

发表于 2019-09-07 10:53:14 回复(1)
/**
*    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> array = new ArrayList<Integer>();
        if(listNode ==  null)
            return array;
        if(listNode.next == null){
            array.add(listNode.val);
            return array;
        }
        ListNode node = listNode;
        while(node.next.next != null){
            node = node.next;
        }
        int n = node.next.val;
        node.next = null;
        array = printListFromTailToHead(listNode);
        array.add(0, n);
        return array;
    }
}

编辑于 2019-09-03 16:11:53 回复(0)
我的想法是:
1、直接让ListNode实现Iterator;
2、在主方法中先遍历ListNode,存到一个临时ArrayList a中,并转成数组b;
3、ArrayList a指向的对象就没用了,直接new 一个新的ArrayList备用(我测了下直接new比clear时间成本低);
4、倒序遍历数组b,将数据逐个存入ArrayList a中,返回a即可;
(
import java.util.ArrayList;
import java.util.Iterator;
class ListNode implements Iterator{
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }


    @Override
    public boolean hasNext() {
        return next!=null;
    }

    @Override
    public Object next() {
        return next;
    }

    public void setNext(Integer integer) {
        this.next=new ListNode(integer);
    }
}

public class Solution {

    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList a=new ArrayList();
        if(listNode==null) return a;
        a.add(listNode.val);
        while (listNode.hasNext()){
            listNode=listNode.next;
            a.add(listNode.val);
        }
        Object[] objects = a.toArray();
        a.clear();
        for (int i=objects.length-1;i>=0;i--){
            a.add(objects[i]);
        }
        return a;

    }
}


发表于 2019-08-31 22:49:41 回复(0)
Collections工具类本身拥有反转list功能,所以使用它
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
//避免listNode是空链表,所以用try-catch语句块
try{
//遍历有效节点,并将其val值加入到list集合
while(listNode.next!=null){
list.add(listNode.val);
listNode = listNode.next;
}
//添加最后一个节点
list.add(listNode.val);
//反转list中的元素
Collections.reverse(list);
}catch(Exception e){
//返回空集合
return list;
}
return list;
}
}
编辑于 2019-08-30 22:33:08 回复(0)
public ArrayList<Integer> printListFromTailToHead(ListNode listNode)
{
    LinkedList<Integer> list = new LinkedList<>();
    while (listNode != null)
    {
        list.addFirst(listNode.val);
        listNode = listNode.next;
    }
    return new ArrayList<>(list);
}
不需要递归,不需要逆序,直接用标准库里的链表的addFirst()方法来搞定
发表于 2019-08-28 19:43:57 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> arr = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null){
            return arr;
        }
        arr.add(0,listNode.val);
        printListFromTailToHead(listNode.next);
        return arr;
    }
}
发表于 2019-08-27 10:36:19 回复(0)