今天是《剑指Offer》系列的第二天，主要内容是链表，题目还是比较容易的，三道题，两道简单一道中等，加油。
从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reverse(ListNode *head, vector<int> &ans){
if(head == nullptr)return;
reverse(head->next, ans);
ans.push_back(head->val);
}
vector<int> reversePrint(ListNode* head) {
vector<int> ans;
if(head == nullptr)return ans;
reverse(head->next, ans);
ans.push_back(head->val);
return ans;
}
};
算法思路：
这道题是要求是从尾到头输出，第一想到的就是栈，栈有先进后出的特性，该题用栈存储就可以很容易地解决，而解法一用的是递归，其实也是栈的一种，对于题一来说有点小题大作，但递归也是栈的一种，而且递归可扩充性很强，遇到比较复杂一点的题在原本的框架上稍加修改就能解决。
ps：这题其实要容易有很多解法，比如直接存数组然后反转还有直接用栈，题目太简单了，所以不详细说。
反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制：
0 <= 节点个数 <= 5000
解法一：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode *head){
if(head->next == nullptr)return head;
ListNode *h = reverse(head->next);
head->next->next = head;
head->next = nullptr;
return h;
}
ListNode* reverseList(ListNode* head) {
if(head == nullptr)return nullptr;
return reverse(head);
}
};
算法思路：
和第一题相比，第二题加了next指针指向的改变，在第一题框架的基础上，我在函数上加了个返回值，返回的是链表反转后的头指针，而函数传递的参数是要反转的链表，调用reverse(head->next)后，以head->next为头的链表已经反转完成且head->next成为反转后的尾结点，此时只需对head->next->next修改一下则完成反转。
解法二：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *pre = nullptr, *p = head;
while(p){
ListNode *tmp = p->next;
p->next = pre;
pre = p;
if(tmp != nullptr){
p = tmp;
}else{
return p;
}
}
return nullptr;
}
};
算法思路：
遍历每个结点然后将结点指向pre结点。
复杂链表的复制
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000Node.random为空（null）或指向链表中的节点。- 节点数目不超过
1000。
解法一：
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr)return nullptr;
Node *ans = new Node(head->val), *p = head->next, *p1 = ans;
ans->random = head->random;
map<Node*, Node*> mp;
mp[head] = ans;
while(p){
Node * nn = new Node(p->val);
mp[p] = nn;
nn->next = p->next;
nn->random = p->random;
p1->next = nn;
p = p->next;
p1 = p1->next;
}
p = head, p1 = ans;
while(p1){
if(p1->random != nullptr)p1->random = mp[p1->random];
p = p->next;
p1 = p1->next;
}
return ans;
}
};
算法思路：
链表的复制比较简单，重点是random指针的改变，我用的是hash算法存储前后两个链表对应结点的关系，然后再一一转换，还是比较容易的，就是hash会占用较大的空间。
解法二：
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr)return nullptr;
Node *p = head, *ans;
while(p){
Node *nn = new Node(p->val);
nn->next = p->next;
p->next = nn;
p = nn->next;
}
p = head;
while(p){
if(p->random != nullptr)p->next->random = p->random->next;
else p->next->random = nullptr;
p = p->next->next;
}
p = head;
ans = head->next;
while(p){
Node* tmp = p->next;
p->next = p->next->next;
p = p->next;
if(tmp->next != nullptr)tmp->next = tmp->next->next;
}
return ans;
}
};
算法思路：
解法二比较巧妙，每个新生成的结点并没有脱离原链表，而是接在老结点后面，复制一遍链表后，对偶数位的结点上的random指针进行修改，然后再对所有结点的next指针进行修改，分别改为指向下一个结点的下一个结点，就是奇偶位的结点分开，分成两个链表，奇结点为旧链表，偶结点则为答案。
最后
今天的题依旧比较简单，考察的是链表的应用，希望我的博客能对你有所帮助。
新人博主发博，恳请各位不吝赐教，不胜感激，晚安。
【剑指Offer】系列：
【剑指Offer】栈