剑指offer 06. 从尾到头打印列表 (easy)
#pragma once
#include<vector>
#include<stack>
using std::vector;
using std::stack;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
/* (先反转链表(迭代)后打印)
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
ListNode* p = head, * q = head; // p为原链表head，q为反转链表的headf （q起始为head，即原链表第一个头节点）
while (p != nullptr) { // 遍历整个原链表
if (p == head) { // 如果是原链表第一个头节点，要特殊处理
p = p->next; // p先向后移动指向原链表下一个结点（即第二结点）
q->next = nullptr; // q->next==nullptr（即将原链表的第一个头节点 作为此时反转链表的头节点，也是尾结点，next为nullptr）
continue;
}
ListNode* t = p->next; // 保存原链表中p->next（即p指向结点的下一个结点地址）
p->next = q; // 关键: 这一步将原链表p指向结点 指向反转链表头节点q，从而p指向结点变为 反转链表的头结点 （每次循环都将原链表中的头节点p 转移到反转链表中）
q = p; // 此时反转链表头节点q为 原链表头节点p
p = t; // 转移后的 原链表头节点为 t指向的结点
}
vector<int> vec;
while (q != nullptr) { // 遍历反转后的链表 并逐个将值val插入到vec中
vec.push_back(q->val);
q = q->next;
}
return vec;
}
};
*/
// 使用栈
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
stack<int> stk;
while (head != nullptr) { // 顺序遍历链表，将每个结点值 push到栈stk中
stk.push(head->val);
head = head->next;
}
vector<int> vec;
while (!stk.empty()) {
vec.push_back(stk.top()); // 利用栈的特性，将栈中的元素出栈 并存储在vec中
stk.pop();
}
return vec;
}
};
剑指offer 24. 反转链表 (easy)
#pragma once
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
/* (迭代)
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* p = nullptr;
while (head != nullptr) { // 遍历整个原链表
ListNode* t = head->next; // 保存原链表中head->next（即head指向结点的下一个结点地址）
head->next = p; // 关键: 这一步将原链表head指向结点 指向反转链表头节点p，从而head指向结点变为 反转链表的头结点 （每次循环都将原链表中的头节点head 转移到反转链表中）
p = head; // 此时反转链表头节点p为 原链表头节点head
head = t; // 转移后的 原链表头节点为 t指向的结点
}
return p;
}
};
*/
// (递归)
class Solution {
private:
ListNode* rhead; // 用来记录反转链表后的头节点，也就是原链表的尾结点
public:
ListNode* dg(ListNode* head);
ListNode* reverseList(ListNode* head) {
dg(head);
return rhead;
}
};
ListNode* Solution::dg(ListNode* head) {
if (head == nullptr || head->next == nullptr) { // 递归到最后一个结点返回 （注意链表为空的情况）
rhead = head; // 记录原链表的尾结点（即反转链表的头节点）
return head;
}
ListNode* head_next = dg(head->next); // 函数dg返回的结点即head->next，即当前结点的下一个结点
head_next->next = head; // 当前结点的下一个结点指向自己
head->next = nullptr; // 自己的next设为nullptr （head此时是 当前反转链表的尾结点）
return head; // 传进来是head，返回的也是head（该法的核心在于，必须从原链表尾部往前反转，而不能从原链表头部往后反转）
}
剑指offer 35. 复杂链表复制 (medium)
#pragma once
#include<unordered_map>
#include<iostream>
using std::unordered_map;
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
/* 直接法 （先构造复制链表，再查找并设置random指针）
class Solution {
public:
Node* copyRandomList(Node* head) {
Node* dummy = new Node(0); // 复制的链表的dummy结点 （即head头节点的前一个结点）
Node* cur = head; // cur指向当前结点
Node* pre = dummy; // pre指向"当前复制链表"的最后一个结点，也就是下一个新结点p的前一个结点
while (cur != nullptr) { // 遍历整个原链表，构造复制的链表结点和next指针 （random指针无法在 构造链表的过程中 设置，因为random指向的结点 可能还未构造）
Node* p = new Node(cur->val); // new一个新结点p，其值val与原链表中对应的结点相同
p->next = nullptr; // p的next设为nullptr （结点p将要是"当前复制链表"的尾结点）
pre->next = p; // 将结点p接在"当前复制链表"尾部
pre = p; // pre赋值为p，即向后移动 （因此pre又指向"当前复制链表"的最后一个结点）
cur = cur->next;
}
for (Node* p = head, *q = dummy->next; p != nullptr; p = p->next, q = q->next) { // p和q分别指向原链表和复制链表，同时遍历两条链表，设置复制链表的结点的random指针
Node* random = p->random; // random为原链表中 p指向结点的random指针
int distence = 0;
for (Node* i = head; i != random; i = i->next) { // 计算random指针指向的结点 离头节点的距离distence
++distence;
}
Node* j = dummy->next;
while (distence != 0) { // 根据距离distence在复制链表中 找到相应的结点的指针j
j = j->next;
--distence;
}
q->random = j; // 因此q指向结点 的random指针为j
}
return dummy->next;
}
};
*/
/* 利用map存储 原链表结点指针和复制链表结点指针 的键值对 （相比上面方法更巧妙，无需计算距离和根据距离查找random，时间复杂度从N*N下降到N）
class Solution {
public:
Node* copyRandomList(Node* head) {
unordered_map<Node*, Node*> hash;
for (Node* cur = head; cur != nullptr; cur = cur->next) { // 遍历原链表
Node* node_p = new Node(cur->val); // 先创建结点，并建立map中 原链表结点指针和复制链表结点指针 的映射关系
hash[cur] = node_p;
}
for (Node* cur = head; cur != nullptr; cur = cur->next) { // 遍历原链表
hash[cur]->next = hash[cur->next]; // 设置之前创建的 复制结点的next和random指针 （因为是复制链表，所以复制结点的next,random指针 指向结点的位置 与原链表相应结点的next,random指针指向结点位置 是相对应的）
hash[cur]->random = hash[cur->random]; // 根据原结点和复制结点的 这种映射关系，可以用来设置 复制结点的next和random指针
}
return hash[head];
}
};
*/
// 拼接+拆分（将复制结点插入 原链表中对应结点的后面，根据位置对应关系 并结合拼接链表，就能够通过一次遍历链表来设置 复制链表的结点的random，之后再拆分从而得到复制链表）
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
for (Node* cur = head; cur != nullptr; cur = cur->next->next) { // 拼接（将复制结点插入原链表的 cur指向的结点后面）
Node* node_p = new Node(cur->val);
node_p->next = cur->next;
cur->next = node_p;
}
for (Node* cur = head; cur != nullptr; cur = cur->next->next) { // 设置复制链表的结点的random指针（根据位置对应关系 并结合拼接链表知: 复制结点的random即 "cur指向结点的random指针指向结点 之后的结点的指针"）
if (cur->random != nullptr) {
cur->next->random = cur->random->next;
}
}
Node* pre = head, * cur = head->next, * copy_head = head->next; // 拆分 （将原链表和复制链表拆分）
while (pre->next->next != nullptr) {
pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr; // 注意！虽然我们返回的是复制链表，但是拆分后的 原链表的尾结点next指针必须设置为nullptr，否则会出错！
return copy_head;
}
}; 官方题解：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/fu-za-lian-biao-de-fu-zhi-by-leetcode-so-9ik5/
京公网安备 11010502036488号