济宁做网站有哪几家,photolux wordpress,乐陵森司特木业,展台展馆设计搭建title: 剑指 Offer 06. 从尾到头打印链表 tags:
链表递归迭代 categories:算法剑指 Offer 题目描述
输入一个链表的头节点#xff0c;从尾到头反过来返回每个节点的值#xff08;用数组返回#xff09;。
示例 1#xff1a;
输入#xff1a;head [1,3,2]
输出#…
title: 剑指 Offer 06. 从尾到头打印链表 tags:
链表递归迭代 categories:算法剑指 Offer 题目描述
输入一个链表的头节点从尾到头反过来返回每个节点的值用数组返回。
示例 1
输入head [1,3,2]
输出[2,3,1]
限制
$0 链表长度 10000$ 算法 1
(迭代) $O(n)$
从前往后遍历链表存储每个节点的值到答案数组中然后反转答案数组就是从尾到头打印链表的结果。
时间复杂度
$O(n)$
空间复杂度
$O(n)$
C 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vectorint reversePrint(ListNode* head) {vectorint res;for (auto p head; p; p p-next) res.push_back(p-val);reverse(res.begin(), res.end());return res;}
};
Java 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {public int[] reversePrint(ListNode head) {ListInteger resList new ArrayList();ListNode p head;while (p ! null) {resList.add(p.val);p p.next;}Collections.reverse(resList);int[] res new int[resList.size()];for (int i 0; i resList.size(); i ) {res[i] resList.get(i);}return res;}
}
Python 代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def reversePrint(self, head: ListNode) - List[int]:res_list []p headwhile p:res_list.append(p.val)p p.nextreturn res_list[::-1]
算法 2
(递归) $O(n)$
递归的出口条件当前节点为空返回空数组。 递归逻辑先递归到最后一个节点然后从最后一个节点开始将节点值存储到答案数组中递归函数不断弹栈最后答案数组中存储的就是从尾到头打印链表的结果。
时间复杂度
$O(n)$
空间复杂度
存储答案的空间 $O(n)$包含递归系统栈所需的空间 $O(n)$。
C 代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:vectorint res;vectorint reversePrint(ListNode* head) {if (!head) return {};reversePrint(head-next);res.push_back(head-val);return res;}
};
Java 代码
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val x; }* }*/
class Solution {ListInteger res new ArrayList();public int[] reversePrint(ListNode head) {reverseList(head);int[] result new int[res.size()];for (int i 0; i res.size(); i ) {result[i] res.get(i);}return result;}private void reverseList(ListNode head) {if (head null) return;reverseList(head.next);res.add(head.val);}
}
Python 代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val x
# self.next Noneclass Solution:def reversePrint(self, head: ListNode) - List[int]:self.res []def reverseList(node):if not node:returnreverseList(node.next)self.res.append(node.val)reverseList(head)return self.res
推荐阅读
https://www.mianshi.onlinehttps://www.i9code.cn 本文由博客一文多发平台 OpenWrite 发布
