Java 详解如何从尾到头打印链表

1.题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

题目来源：力扣（LeetCode）

2.解法

2.1栈

栈的特点是先进后出，所以我们创建一个栈，逐个将节点压入栈内，然后建立一个数组，将栈内的节点数值逐个弹出

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();//创建一个栈
        ListNode cur = head;
        //将节点压栈
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        int size = stack.size();//栈的长度
        int[] array = new int[size];//创建一个和栈一样长的数组
        //出栈入数组
        for (int i = 0; i < size; i++) {
            array[i] = stack.pop().val;
        }
        return array;
    }
}

2.2递归

public class PrintList {
  
    ArrayList<Integer> cur = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] array = new int[cur.size()];
        for (int i = 0; i <array.length; i++) {
            array[i] = cur.get(i);
        }
        return array;
 
    }
 
    public void recur(ListNode head) {
        if(head == null) {
            return ;
        }
        recur(head.next);
        cur.add(head.val);
    }
 
}

3.复杂度

3.1栈

时间复杂度：O(n)。正向遍历一遍链表，然后从栈弹出全部节点，等于又反向遍历一遍链表。空间复杂度：O(n)。额外使用一个栈存储链表中的每个节点。

3.2递归

时间复杂度：O(n) 遍历链表，递归 NN次。

空间复杂度：O(n) 系统递归需要使用 O(N)的栈空间

频道导航