Day2 2022.11.8 链表（简单）
06.从尾到头打印链表
自己实现
通过链表的next遍历链表并将每一个值都存进vector里面，遍历完之后再用for(i=0;i<res.size()/2;i++)来手动倒置
代码如下
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> reversePrint(ListNode* head) {
vector<int> res;
ListNode* now=head;
if(now==NULL)return res;
while(now!=NULL)
{
res.push_back(now->val);
now=now->next;
}
for(int i=0;i<res.size()/2;i++)
{
int temp;
temp=res[i];
res[i]=res[res.size()-1-i];
res[res.size()-1-i]=temp;
}
return res;
}
};
代码表现
时间复杂度还是不够低呀
题解
递归法
使用以下代码来递归遍历链表，以便能够按照尾->头的顺序存储进数组中，就不用倒置了
void recur(ListNode head) {
if(head == null) return;
recur(head.next);
vec.push_back(head.val);
}
代码表现
0ms，nb。。。就是内存耗得较多
hint：
- 单独判断空输入的情况。不能简单使用while(now!=NULL)就认为万无一失，要考虑now带着NULL跨过这个while会对后面的程序有什么影响
- 递归的实质就是一个栈，先进后出
24.反转链表
自己实现
参考上一道题的“递归法”，用递归来将原链表的next反向，设置最尾元素为头节点，然后递归地设置next回来，思路其实一样
代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
int flag;
ListNode* h;
public:
ListNode* reverseList(ListNode* head) {
flag = 0;
recur(head, NULL);
return h;
}
void recur(ListNode* now, ListNode* addr)
{
if (now == NULL)return;
recur(now->next, now);
if (flag == 0)
{
flag = 1;
h = now;
//return;
}
now->next = addr;
return;
}
};
代码表现
题解：
方法一：迭代（所需时间比递归高）
使用双指针，正向地一步步地把next调整过来，并用另外一个tmp指针存储将要调整next的节点的原next节点。
代码如下：
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur=head;
ListNode* pre=NULL;
ListNode* tmp;
while(cur!=NULL)
{
tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
代码表现
时间表现没有递归好，空间表现不错
hint：
- 解决链表的next断了之后就找不到前一个点的地址的方法就是在递归函数多加一个参数，将前一个节点的地址通过参数进行传递给下一个节点的递归过程中，方便下一节点链接回来
- 注意在主函数中第一次开始调用递归函数的参数设置，很重要
35.复杂链表的复制
自己实现：
因为该题目不能使用一次遍历原链表就能做完，因此自己实现想到的思路时间复杂度较高（即先获取原链表的random对应第几个节点，存储该信息，然后在新链表中对节点按顺序进行编号，然后遍历原链表中的对应信息，再对新链表的random赋值），可能高达O(N2)，不可行，没有再写
题解：
方法一：哈希表
-
若头节点
head为空节点，直接返回null； -
初始化：哈希表
dic，节点cur指向头节点； -
复制链表：
a. 建立新节点，并向
dic添加键值对（原cur节点，新cur节点）；b.
cur遍历至原链表下一节点 -
构建新链表的引用指向
a. 构建新节点的
next和random引用指向；b.
cur遍历至原链表下一节点； -
返回值：新链表的头节点
dic[cur]；
代码如下：
/*
// 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) {
unordered_map<Node*,Node*> map;
Node* now=head;
Node* head0=new Node(0);
Node* now0=head0;
while(now!=NULL) //travel origin list to create pair within map
{
Node* tmp=new Node(0);
tmp->val=now->val;
map.insert(pair<Node*,Node*> (now,tmp));
now=now->next;
}
now=head;
while(now!=NULL)
{
map[now]->next=map[now->next];
map[now]->random=map[now->random];
now=now->next;
}
return map[head];
}
};
代码表现
时间表现不错
方法二：拼接 + 拆分
考虑考虑构建原节点 1 -> 新节点 1 -> 原节点 2 -> 新节点 2 -> …… 的拼接链表，如此便可在访问原节点的 random指向节点的同时找到新对应新节点的random指向节点。
-
复制各节点，构建拼接链表
设原链表为node1 -> node2 -> …，构建的拼接链表：node1 -> node1new -> node2 -> node2new -> …
-
构建新链表各节点的
random指向：当访问原节点
cur的随机指向节点cur.random时，对应新节点cur.next的随机指向节点为cur.random.next(*重要) -
拆分原 / 新链表：
设置
pre/cur分别指向原 / 新链表头节点，遍历执行pre.next = pre.next.next和cur.next = cur.next.next将两链表拆分开（两个操作顺序依次一起执行） -
返回新链表的头节点
res即可
代码如下（直接搬运题解的，因为感觉思路和映射一样，只是处理过程不同，感觉还复杂了些…）
class Solution {
public:
Node* copyRandomList(Node* head) {
if(head == nullptr) return nullptr;
Node* cur = head;
// 1. 复制各节点，并构建拼接链表
while(cur != nullptr) {
Node* tmp = new Node(cur->val);
tmp->next = cur->next;
cur->next = tmp;
cur = tmp->next;
}
// 2. 构建各新节点的 random 指向
cur = head;
while(cur != nullptr) {
if(cur->random != nullptr)
cur->next->random = cur->random->next;
cur = cur->next->next;
}
// 3. 拆分两链表
cur = head->next;
Node* pre = head, *res = head->next;
while(cur->next != nullptr) {
pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr; // 单独处理原链表尾节点
return res; // 返回新链表头节点
}
};
代码表现：
hint：
-
复制链表的示例代码（可多看熟悉步骤）
class Solution { public: Node* copyRandomList(Node* head) { Node* cur = head; Node* dum = new Node(0), *pre = dum; //Node构造函数是对该节点val赋值 while(cur != nullptr) { Node* node = new Node(cur->val); // 复制节点 cur pre->next = node; // 新链表的 前驱节点 -> 当前节点 cur = cur->next; // 遍历下一节点 pre = node; // 保存当前新节点 } return dum->next; } }; -
因为要将原链表复制到新链表，所以是一一映射的关系，这种情况下多采用哈希表。(unordered_map<> in c++)
原文地址：http://www.cnblogs.com/cspzyy/p/16884277.html
