东营建设信息网站,详情页设计说明,江西省赣州市南康家具城,wordpress restfulapi目录剑指 Offer 06. 从尾到头打印链表剑指 Offer 24. 反转链表剑指 Offer 35. 复杂链表的复制剑指 Offer 06. 从尾到头打印链表 原题链接#xff1a;06. 从尾到头打印链表 最容易想到的思路就是先从头到尾打印下来#xff0c;然后 reverse 一下#xff0c;但这里我们使用递归…
目录剑指 Offer 06. 从尾到头打印链表剑指 Offer 24. 反转链表剑指 Offer 35. 复杂链表的复制剑指 Offer 06. 从尾到头打印链表 原题链接06. 从尾到头打印链表 最容易想到的思路就是先从头到尾打印下来然后 reverse 一下但这里我们使用递归。
class Solution {
public:vectorint reversePrint(ListNode *head) {if (head nullptr) return {};auto res reversePrint(head-next);res.push_back(head-val);return res;}
};递归的缺点是元素一多容易爆栈我们还可以利用栈的特性来完成这道题。
剑指 Offer 24. 反转链表 原题链接24. 反转链表 递归解法清晰易懂
class Solution {
public:ListNode *reverseList(ListNode *head) {if (!head || !head-next) return head;auto newHead reverseList(head-next);head-next-next head;head-next nullptr;return newHead;}
};当链表长度为 000 或 111 时无需反转。
考虑链表 1→2→3→4→∅1\to2\to3\to4\to\varnothing1→2→3→4→∅当调用 reverseList(1-next) 后链表变成 1→2←3←41\to2\leftarrow3\leftarrow41→2←3←4此时需要让 222 指向 111即 2-next 1相当于 1-next-next 1之后还需要让 111 指向 ∅\varnothing∅即 1-next nullptr。
迭代解法
class Solution {
public:ListNode *reverseList(ListNode *head) {ListNode *pre nullptr;ListNode *cur head;while (cur) {ListNode *tmp cur-next;cur-next pre;pre cur;cur tmp;}return pre;}
};设置两个指针每次让后一个节点指向前一个节点然后两个指针同时右移一位。
剑指 Offer 35. 复杂链表的复制 原题链接35. 复杂链表的复制 我们先来看一下普通链表是如何复制的。
class Node {
public:int val;Node *next;Node() : val(0), next(nullptr) {}Node(int _val) : val(_val), next(nullptr) {}Node(int _val, Node *_next) : val(_val), next(_next) {}
};class Solution {
public:Node *copyList(Node *head) {Node *cur head;Node *dummy new Node(-1), *pre dummy;while (cur) {Node *newNode new Node(cur-val);pre-next newNode;cur cur-next, pre pre-next; // cur在原链表上移动pre在新链表上移动}return dummy-next;}
};因为普通链表只有一个 next 指针且指向下一个节点所以我们可以用迭代的方法复制一个普通链表当然也可以递归。但是复杂链表还有一个 random 指针指向随机一个节点所以迭代方法失效。
我们可以通过哈希表来建立原链表和新链表之间的对应关系具体来说map[原链表中的某个节点] 新链表中相应的节点这样就可以随机访问新链表中的节点了。
class Solution {
public:Node *copyRandomList(Node *head) {if (!head) return head;unordered_mapNode *, Node * map;Node *cur head;while (cur) {map[cur] new Node(cur-val);cur cur-next;}cur head;while (cur) {map[cur]-next map[cur-next];map[cur]-random map[cur-random];cur cur-next;}return map[head];}
};
