怎样做网站赚钱,网站做网络营销,专业的外贸网站建设,国内外网站开发的现状问题描述1
给你一个链表#xff0c;两两交换其中相邻的节点#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题#xff08;即#xff0c;只能进行节点交换#xff09;。
求解
使用一个栈S来存储相邻两个节点即可
/*** Definition for…问题描述1
给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
求解
使用一个栈S来存储相邻两个节点即可
/*** Definition for singly-linked list.* 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* swapPairs(ListNode* head) {stackListNode* s;if(headnullptr || head-next nullptr){return head;}ListNode * p new ListNode();ListNode * cur head;head p;while(cur!nullptr cur-next !nullptr){s.push(cur);s.push(cur-next);cur cur-next-next;p-next s.top();s.pop();p p-next;p-next s.top();s.pop();p p-next;}if(curnullptr){p-next nullptr;}else if(cur-next nullptr){p-next cur;}return head-next;}
};问题描述2
给你一个长度为 n 的链表每个节点包含一个额外增加的随机指针 random 该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如如果原链表中有 X 和 Y 两个节点其中 X.random -- Y 。那么在复制链表中对应的两个节点 x 和 y 同样有 x.random -- y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示
val一个表示 Node.val 的整数。 random_index随机指针指向的节点索引范围从 0 到 n-1如果不指向任何节点则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
求解
使用哈希表。 利用哈希表的查询特点考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系再遍历构建新链表各节点的 next 和 random 引用指向即可。
/*
// 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(headNULL){return NULL;}unordered_mapNode*, Node* mp;Node * cur head;while(cur!NULL){mp[cur] new Node(cur-val);cur cur-next;}cur head;while(cur !NULL){mp[cur]-next mp[cur-next];mp[cur]-random mp[cur-random];cur cur-next;}return mp[head];}
};
