首页 > 试题广场 >

从尾到头打印链表

[编程题]从尾到头打印链表
  • 热度指数:1694578 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个链表的头节点,按链表从尾到头的顺序返回每个节点的值(用数组返回)。

输入{1,2,3}的链表如下图:
返回一个数组为[3,2,1]

0 <= 链表长度 <= 10000
示例1

输入

{1,2,3}

输出

[3,2,1]
示例2

输入

{67,0,24,58}

输出

[58,24,0,67]

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
推荐
方法一:链表从尾到头输出,利用递归实现,不使用库函数直接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 回复(73)
import java.util.*;
/**
*    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> initLinkedList = new ArrayList<>();
        ListNode temptNode = listNode;
        while (temptNode != null) {
            initLinkedList.add(temptNode.val);
            temptNode = temptNode.next;
        }
        temptNode = listNode;
        ArrayList<Integer> reversedLinkedList = new ArrayList<>();
        ListNode reversedListNode = reversedLinkedList(listNode);

        while (reversedListNode != null) {
            reversedLinkedList.add(reversedListNode.val);
            reversedListNode = reversedListNode.next;
        }

        return reversedLinkedList;

    }
    public static ListNode reversedLinkedList(ListNode listNode) {
        if (listNode == null || listNode.next == null) {
            return listNode;
        } else {
            ListNode temptNode = listNode;
            ListNode priorNode = null;
            ListNode nextNode = listNode.next;
            while (nextNode.next != null) {
                priorNode = temptNode;
                temptNode = nextNode;
                nextNode = nextNode.next;
                temptNode.next = priorNode;
            }
            nextNode.next = temptNode;
            listNode.next = null;
            listNode = nextNode;
            return listNode;
        }
    }
}


编辑于 2024-02-17 17:45:21 回复(0)

1.利用头插法直接逆置链表

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList printListFromTailToHead(ListNode listNode) {
        if(listNode == null){
            return new ArrayList();
        }
        ListNode next = null;
        ListNode prev = null;
        while(listNode != null){
            next = listNode.next;
            listNode.next = prev;
            prev = listNode;
            listNode =next;
        }
        listNode = prev;
        ArrayList reslut = new ArrayList();
        while(listNode != null){
            reslut.add(listNode.val);
            listNode = listNode.next;
        }
        return reslut;
    }
}

2.新建数组保存值,之后逆置数组

import java.util.*;
/**
*    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> resultList = new ArrayList<>();
       while(listNode != null){
        resultList.add(listNode.val);
        listNode = listNode.next;
       }
       ArrayList<Integer> midList = new ArrayList<>();
       for(int i = resultList.size()-1; i >= 0;i--){
        midList.add(resultList.get(i));
       }

       return midList;   
    }
}
发表于 2023-12-17 15:28:51 回复(0)
最优解:链表利用数组原地翻转
import java.util.*;
/**
*    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) {
        //原地调换位置(链表反转)
        if(listNode == null){
            return new ArrayList<Integer>(0);
        }
        int count = 0;
        ListNode tmp = listNode;
        while(tmp != null){
            count++;
            tmp = tmp.next;
        }
        int[] res = new int[count];
        int k = count - 1;
        while(listNode != null){
            res[k--] = listNode.val;
            listNode = listNode.next;
        }
        ArrayList<Integer> arr = new ArrayList<Integer>();
        for(int i = 0;i < res.length;i++){
            arr.add(res[i]);
        }
        return arr;
    }
}


发表于 2023-11-05 00:02:58 回复(0)
import java.util.*;
/**
*    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) {
        // 方法四:利用头插法 
        ListNode head=new ListNode(-1) ;
        while(listNode!= null){
               //把新加入的节点当做node
               ListNode temp=listNode.next; //需要先把下一个节点的值存储起来,不然就会失效
               listNode.next=head.next;
               head.next=listNode;
               listNode=temp;
        }
        ArrayList <Integer> res = new ArrayList<Integer>();
        head=head.next; 
        while(head!=null){  //访问这个新链表的值即可
            res.add(head.val);
            head=head.next;
        }
        return res;


/*
        // 方法三:利用递归 访问改节点则需访问该节点的子节点
         ArrayList <Integer> res=new ArrayList<Integer>();//定义在方法外边

        if (listNode != null) {
            printListFromTailToHead(listNode.next);
            res.add(listNode.val);
        }
        return res;


        // 方法二:利用Aarraylist.add( index,value)方法来实现
        
        ArrayList <Integer> res=new ArrayList<Integer>();
        while (listNode!=null){
        res.add(0,listNode.val);
        listNode=listNode.next;
        }
        return res;
        

             //方法一:利用栈,从头到尾依次入栈,然后依次出栈
             ArrayList<Integer> res=new ArrayList<Integer>();
             Stack<ListNode> stack =new Stack<ListNode>();
             while(listNode != null){
                 stack.add(listNode);
                 listNode=listNode.next;
             }
             while(stack.size()>0){
                 res.add(stack.pop().val);
             }
             return res;

          */



    }
}

发表于 2023-08-28 17:45:57 回复(0)
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;
    }
}

发表于 2023-06-14 10:02:53 回复(0)
ArrayList本身也可以实现类似栈的功能,list.add(0, xxx)即可插入头部
这样的话代码就非常简洁,只需遍历链表,每个节点的值从头插入数组即可
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(listNode != null){
            res.add(0,listNode.val);
            listNode = listNode.next;
        }
        return res;
    }
}



发表于 2023-06-10 10:16:45 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<IntegerprintListFromTailToHead(ListNode listNode) {

           ArrayList<Integerlist=new ArrayList<Integer>();
           if(listNode!=null){
               getList(list,listNode);
           }
           return list;
        
    }

    public ArrayList<Integer>  getList(ArrayList<Integerlist,ListNode listNode){
          if(listNode.next==null){
              list.add(listNode.val); 
              return list;
          }else{
              list=getList(list,listNode.next);
              list.add(listNode.val);
              return list;
          }
    }
}
发表于 2022-12-01 19:47:09 回复(0)
import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        while(listNode != null) {
            res.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(res);
        return res;
    }
}
发表于 2022-09-15 14:11:55 回复(0)
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        while(listNode!=null){
            list.add(listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}
发表于 2022-08-31 16:00:20 回复(0)
import java.util.*;
/**
*    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();
        while(listNode != null){
            list.add(0,listNode.val);
            listNode = listNode.next;
        }
        return list;
    }
}

发表于 2022-08-24 17:29:42 回复(0)
public class Solution {
    private ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        reserve(listNode);
        return list;
    }

    private void reserve(ListNode listNode) {
        if (listNode == null) {
            return;
        }
        reserve(listNode.next);
        list.add(listNode.val);
    }
}

发表于 2022-08-17 11:11:00 回复(0)
import java.util.*;
 
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //多使用一个栈的数据结构,使节点值逆序
        //时间复杂度为O(N),空间复杂度O(N)
        Stack<Integer> s=new Stack<Integer>();
        ArrayList<Integer> res=new ArrayList<>();
        while(listNode!=null){
            s.push(listNode.val);
            listNode=listNode.next;
        }
        while(!s.isEmpty()){
            res.add(s.pop());
        }
        return res;
    }
}

发表于 2022-07-30 12:37:15 回复(0)
为什么和答案同样的代码 会显示报错,说数组溢出,多点几次提交又可以了。。。
发表于 2022-07-23 21:37:16 回复(0)
import java.util.*;
/**
*    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 data = new ArrayList<Integer>();
        ListNode cur = listNode;
        while (cur != null) {
            data.add(cur.val);
            cur = cur.next;
        }
        Collections.reverse(data);
        return data;
    }
}
发表于 2022-07-18 22:21:00 回复(0)
import java.util.Collections;
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> ans = new ArrayList<>();
        printListFromTailToHeadCore(ans,listNode);
        return ans;
    }

    private void printListFromTailToHeadCore(ArrayList<Integer> ans, ListNode listNode) {
        if (listNode == null){
            return;
        }
        printListFromTailToHeadCore(ans,listNode.next);
        ans.add(listNode.val);
    }
}

发表于 2022-05-23 11:43:43 回复(0)
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> listres= new ArrayList();
        while(listNode != null){         
            int i = 0;
            listres.add(i,listNode.val);
            i++;
            listNode = listNode.next;
        }
        return listres;
    }
}

发表于 2022-04-23 05:18:38 回复(1)