【剑指offer】06. 从尾到头打印链表

题目描述

力扣

牛客

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

题解

牛客

// 逐元素存储
// 时间复杂度：14ms
// 空间复杂度：9524KB
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> array = new ArrayList<>();
        while (listNode != null) {
            array.add(listNode.val);
            listNode = listNode.next;
        }
        Collections.reverse(array);
        return array;
    }
}

// 时间复杂度：13ms
// 空间复杂度：9528kB
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		Stack<Integer> stack = new Stack<>();
		while (listNode != null) {
			stack.add(listNode.val);
			listNode = listNode.next;
		}
		ArrayList<Integer> ret = new ArrayList<>();
		while (!stack.isEmpty()) {
			ret.add(stack.pop());
		}
		return ret;
    }
}

// 递归法
// 时间复杂度：12 ms
// 空间复杂度：9384 KB
public class Solution {
	public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
		ArrayList<Integer> ret = new ArrayList<>();
		if (listNode != null) {
			ret.addAll(printListFromTailToHead(listNode.next));
			ret.add(listNode.val);
		}
		return ret;
	}
}

力扣

// 力扣与牛客网不同的是，它需要你返回int[]，而不是ArrayList
// 所以其实是更难了

// 逐元素存储(栈存法)
// 时间复杂度：2 ms , 在所有 Java 提交中击败了 40.69% 的用户
// 空间复杂度：39 MB , 在所有 Java 提交中击败了 91.29% 的用户
import java.util.*;

class Solution {
    public int[] reversePrint(ListNode head) {
		Stack<Integer> stack = new Stack<Integer>();
		ListNode temp = head;
		while (temp != null) {
			stack.push(temp.val);
			temp = temp.next;
		}
		int size = stack.size();
		int[] result = new int[size];
		for (int i = 0; i <= result.length - 1; i++) {
			result[i] = stack.pop();
		}
		return result;
    }
}

// 递归法
// 时间复杂度：2 ms , 在所有 Java 提交中击败了 40.69% 的用户
// 空间复杂度：40.4 MB , 在所有 Java 提交中击败了 6.12% 的用户
import java.util.Arrays;

class Solution {
	
	ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
		recur(head);
		int size = tmp.size();
		int[] result = new int[size];
		for (int i = 0; i <= size - 1; i++) {
			result[i] = tmp.get(i);
		}
		return result;
    }
	
	void recur(ListNode head) {
		if (head != null) {
			recur(head.next);
			tmp.add(head.val);
		}
		else {
			return;
		}
	}
}