输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:
输入:head = [1,3,2]
输出:[2,3,1]
限制:
0 <= 链表长度 <= 10000
import java.util.LinkedList;
class Solution {
/**
* @Title: reversePrint
* @Description: 不使用Java的已有链表结构,而是自己通过哑结点方式实现头插
* @author: itbird
* @date 2022年3月15日 下午3:19:50
* @param head
* @return int[] 时间复杂度: O(N) 空间复杂度: O(N)
*/
public int[] reversePrint(ListNode head) {
if (head == null) {
return new int[0];
}
// 构造哑结点,进行头插
ListNode node = new ListNode(0);
int size = 0;
while (head != null) {
size++;
// 保存哑结点的next
ListNode temp = node.next;
// 将哑结点的next,指向新的节点
node.next = new ListNode(head.val);
// 将哑结点的next.next指向第一步保存的哑结点的next节点
node.next.next = temp;
head = head.next;
}
int[] result = new int[size];
node = node.next;
int i = 0;
while (node != null) {
result[i++] = node.val;
node = node.next;
}
return result;
}
/**
* @Title: reversePrint
* @Description: 使用Java的LinkedList,遍历List,进行头插
* @author: itbird
* @date 2022年3月15日 下午3:19:50
* @param head
* @return int[] 时间复杂度: O(N) 空间复杂度: O(2N)
*/
public int[] reversePrint1(ListNode head) {
if (head == null) {
return new int[0];
}
LinkedList<Integer> linkedList = new LinkedList<>();
while (head != null) {
linkedList.addFirst(head.val);
head = head.next;
}
int[] result = new int[linkedList.size()];
for (int i = 0; i < linkedList.size(); i++) {
result[i] = linkedList.get(i);
}
return result;
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
}