从尾到头打印链表

题目描述

输入一个链表,按链表从尾到头的顺序返回一个ArrayList。

Java数据结构

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/

算法思路

1.按顺序添加链表节点到ArrayList,再将ArrayList反序。

代码实现

import java.util.*;
public class Solution {
    private ArrayList<Integer> res = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode==null)
            return res;
        while(listNode!=null){
            res.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(res);
        return res;
    }
}

2.按顺序将链表节点添加到deque的首部,再将deque转为ArrayList

代码实现

import java.util.*;
public class Solution {
    private Deque<Integer> res = new LinkedList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode==null)
            return new ArrayList<Integer>();
        while(listNode!=null){
            res.addFirst(listNode.val);
            listNode = listNode.next;
        }
        return new ArrayList<Integer>(res);
    }
}

3.递归思想:先添加链表的后半部分,再添加当前节点

代码实现

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;
    }
}