剑指 Offer Day2——链表（简单）

剑指 Offer 06. 从尾到头打印链表

原题链接：06. 从尾到头打印链表

最容易想到的思路就是先从头到尾打印下来，然后 reverse 一下，但这里我们使用递归。

class Solution {
public:vector<int> 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;}
};

当链表长度为 $0$ 或 $1$ 时，无需反转。

考虑链表 $1\to 2\to 3\to 4\to \varnothing$，当调用 reverseList(1->next) 后，链表变成 $1\to 2\leftarrow 3\leftarrow 4$，此时需要让 $2$ 指向 $1$，即 2->next = 1，相当于 1->next->next = 1，之后还需要让 $1$ 指向 $\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_map<Node *, 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];}
};