剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
示例 1:
输入: head = [1,3,2] 输出:[2,3,1]
限制:
0 <= 链表长度 <= 10000
所给代码如下
/**
1. Definition for singly-linked list.
2. struct ListNode {
3. int val;
4. ListNode *next;
5. ListNode(int x) : val(x), next(NULL) {}
6. };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
}
};
思考:
要把链表元素逆序打印,我现在可以想到实现逆序的有
- 可以数组从尾到头逆序打印
- 可以链表逆置再打印
- 可以用出栈入栈的性质来实现逆序
这题目的标签是栈,数组,链表,双指针,也就是说用栈就行,双指针现在也没有做过相关题目,如果以后接触到了可以回头再考虑这个题目。
画个草图来辅助做题:
![在这里插入图片描述](https://img-blog.csdnimg.cn/33f7e115513246fca973324d4c656438.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5qGD5rWq5Y2B5LiD5Li2,size_20,color_FFFFFF,t_70,g_se,x_16)
步骤已经很明确了,遍历链表元素并且入栈,然后出栈直到栈空。
用代码实现
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> arr;
stack<int> newStack;
ListNode* tmp = head;
while(tmp != nullptr) {
newStack.push(tmp->val);
tmp = tmp->next;
}
while(!newStack.empty()) {
arr.push_back(newStack->top());
newStack.pop();
}
return arr;
}
};
剑指 Offer 24. 反转链表
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
题目给出代码框架:
/**
1. Definition for singly-linked list.
2. struct ListNode {
3. int val;
4. ListNode *next;
5. ListNode(int x) : val(x), next(NULL) {}
6. };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
}
};
思考:
这个题目其实和基本的链表操作没有差多少
![在这里插入图片描述](https://img-blog.csdnimg.cn/4da4ef286c964c71bf8b560eb5472b0c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5qGD5rWq5Y2B5LiD5Li2,size_20,color_FFFFFF,t_70,g_se,x_16)
- 先构造两个结点,pre指向空,current指向head
- 再按照以往的操作基本向后遍历即可
答案
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* currentNode = head;
ListNode* pre = nullptr;
while(currentNode != nullptr) {
ListNode* tmpNode = currentNode->next; // 这是下次移动的位置
currentNode->next = pre; // 把current指向原来next的指针指向pre
pre = currentNode; // pre向后移动到原来current的位置
currentNode = tmpNode; // current向后移到了原来tmp的位置
}
return pre;
}
};
剑指 Offer 35. 复杂链表的复制
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。
示例 1:
![在这里插入图片描述](https://img-blog.csdnimg.cn/f4c2b9e55f8040b29516fceb6082e1fb.png)
输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]
题目给代码框架:
/*
// 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) {
}
};
思考:
- 看到这个题目,首先会想到可以把random随即节点和next节点分开处理
- 这个题目的标签是链表和哈希,但是比较熟悉的是链表操作,比较菜的水平就用菜的方法,直接上链表,搞细胞分裂了
- 细胞分裂是先复制材料再分裂,这个题目也一样,处理next节点和普通的链表插入操作一样
- 创建新节点cpNode,把当前节点的值传给cpNode,然后从头到尾遍历插入即可完成next的复制工作
- 然后处理random,在做这个题目的时候也是不太能理解要怎么写这个代码,还是要感谢一位学长画这个图给我看,瞬间就明白了其实lc官方给的图可以简化成这样来辅助理解
- 细胞分裂材料复制完毕后完就可以进行分裂了。把复制体分开即可
答案
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) {
return nullptr;
}
// 复制next
Node* tempNode = head;
while(tempNode != nullptr) {
Node* cpNode = new Node(tempNode->val);
cpNode->next = tempNode->next;
tempNode->next = cpNode;
tempNode = cpNode->next;
}
// 复制random
tempNode = head;
while(tempNode != nullptr) {
if(tempNode->random != nullptr) {
tempNode->next->random = tempNode->random->next; //正如思考5里画的那样
}
tempNode = tempNode->next->next;
}
// 开始细胞分裂
tempNode = head->next;
Node* pre = head;
Node* cpHead = head->next;
while(tempNode->next != nullptr) {
pre->next = pre->next->next;
tempNode->next = tempNode->next->next;
pre = pre->next;
tempNode = tempNode->next;
}
pre->next = nullptr;
return cpHead;
}
};