本问题对应的 leetcode 原文链接：剑指 Offer 06. 从尾到头打印链表
问题描述
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
代码实现
// 从右边=往左填充
public int[] reversePrint(ListNode head) {
if(head == null)
return new int[0];
// 统计链表节点个数，方便创建数组
int count = 0;
ListNode temp = head;
while(temp != null){
count++;
temp = temp.next;
}
int[] res = new int[count];
int k = count - 1;
// 从由往左填充数组
while(head != null){
res[k--] = head.val;
head = head.next;
}
return res;
}
时间复杂度：O(n)
额外空间复杂度：O(1)
Python
# 从右边往左填充
class Solution(object):
def reversePrint(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
if not head:
return []
# 统计链表节点个数，方便创建数组
count = 0
temp = head
while temp:
count += 1
temp = temp.next
res = [0] * count
k = count - 1
# 从右往左填充数组
while head:
res[k] = head.val
k -= 1
head = head.next
return res
C++
// 从右边往左填充
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
if(!head)
return {};
// 统计链表节点个数，方便创建数组
int count = 0;
ListNode* temp = head;
while(temp){
count++;
temp = temp->next;
}
vector<int> res(count);
int k = count - 1;
// 从右往左填充数组
while(head){
res[k--] = head->val;
head = head->next;
}
return res;
}
};
Go
// 从右边往左填充
func reversePrint(head *ListNode) []int {
if head == nil {
return []int{}
}
// 统计链表节点个数，方便创建数组
count := 0
temp := head
for temp != nil {
count++
temp = temp.Next
}
res := make([]int, count)
k := count - 1
// 从右往左填充数组
for head != nil {
res[k] = head.Val
k--
head = head.Next
}
return res
}
JS
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {number[]}
*/
var reversePrint = function(head) {
if(head == null)
return new Array(0);
// 统计链表节点个数，方便创建数组
let count = 0;
let temp = head;
while(temp != null){
count++;
temp = temp.next;
}
let res = new Array(count);
let k = count - 1;
// 从右往左填充数组
while(head != null){
res[k--] = head.val;
head = head.next;
}
return res;
};
shuaidi
评论(9)
递归 arr=new ArrayList();
class Solution {
ArrayList
public int[] reverseBookList(ListNode head) {
recur(head);
//return arr.toArray();
return arr.stream().mapToInt(Integer::intValue).toArray();
}
void recur(ListNode node){
if(nodenull)
return;
recur(node.next);
arr.add(node.val);
}
}
时间O(n)，空间O(1)
public int[] reversePrint(ListNode head) {
int len = 0;
ListNode cur = head;
while(cur != null){
cur = cur.next;
len++;
}
int[] a = new int[len];
int num = 1;
cur = head;
while(cur != null){
a[len-num] = cur.val;
num++;
cur = cur.next;
}
return a;
}
时间复杂度：O(n)
额外空间复杂度：O(1)
“`java
class Solution {
public int[] reversePrint(ListNode head) {
//方法一 创建指针遍历得到链表的长度 新建一个数组 从尾开始增加链表的值 注意数组的长度和元素的下表不要出错！！
if(head == null){
return new int[0];
}
int count = 0;
ListNode temp = head;
while(temp!=null){
temp = temp.next;
count++;
}
int [] res = new int[count];
int k = count -1;
while(head!=null){
res[k–] = head.val;
head = head.next;
}
return res;
//方法二：利用栈先进后处的特点来完成 stack.add()增加元素 stack.pop()弹出栈内最上面的元素 st = new Stack ();
Stack
int count = 0;
while(head!=null){
st.add(head.val);
head = head.next;
}
int [] res = new int[st.size()];
for(int i =0; i <res.length; i++){
res[i] = st.pop();
}
return res;
}
}
递归。但是list怎么能直接取出数组？
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)
思路一：先反转链表，再遍历，这样就不需要额外的栈空间开销
方法二：使用栈
方法三：就地逆序数组