当前位置：首页 > news >正文

【数据结构】两两交换链表复制带随机指针的链表

news 2025/7/31 22:01:07

问题描述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) {stack<ListNode*> s;if(head==nullptr || 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(cur==nullptr){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(head==NULL){return NULL;}unordered_map<Node*, 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];}
};