[LeetCode OJ] Copy List with Random Pointer 扩大-白红宇

[LeetCode OJ] Copy List with Random Pointer 扩大

阅读量：6174 次

发布时间：2019-06-21

本文共 2474 字，大约阅读时间需要 8 分钟。

职务地址：

题意：对一个有回路的链表的深复制

解题：这道题我AC了之后才发现理解错了题意，然后就參考了以下这篇文章。

假设想看这道题的解题思路的话，请移步

拓展：假如题目给的节点不是链表的头节点。而是链表中的随意一个节点，在保证从给的点能遍历所有节点的情况下，深复制这个链表。

那么该怎么做呢？

思路：事实上一想，和原题的区别仅仅有节点是否是头节点而已，那么我们就从给的这个节点找到原节点即可了。

遍历的过程用dfs，再用map来推断一个节点是否被遍历过。如今唯一的难点就是怎样找到头节点，这里用并查集就OK了。

路径压缩后并查集的复杂度接近O(1),因为map的复杂度接近O(logN),这样dfs的复杂度大概是O(NlogN)。

技巧：dfs到一个新的节点时，用map将其映射成一个唯一的整数cnt，并在这时初始化并查集fa[cnt]。

//#include "stdafx.h"#include
     
      #include
      
       #include 
       #include
        
         using namespace std;int fa[10024];//节点数inline int findfa(int x){    if(fa[x] == x) return x;    while(x!=fa[x]){        x=fa[x];    }    return x;}inline int merge(int x,int y){    int fa1=findfa(x), fa2=findfa(y);    if(fa1!=fa2){        fa[fa2] = fa1;    }    return fa1;}struct RandomListNode {    int label;    RandomListNode *next, *random;    RandomListNode(int x) : label(x), next(NULL), random(NULL) {}};class Solution {    map
         
           mp;    map
          
           ::iterator it; int cnt;public: RandomListNode *copyRandomList(RandomListNode *head) { if(!head) return head; /***********凝视部分是拓展的解法************ init(); dfs(head,1); int faNum = findfa(1); for(it=mp.begin();it!=mp.end();++it){ if(it->second == faNum){ head = it->first; break; } } ***********************************************/ return deepCopy(head); } void init(){ memset(fa,0,sizeof(fa)); cnt=0; } void dfs(RandomListNode *ptr, int faCnt){ if(ptr == NULL) return; it=mp.find(ptr); if(it!=mp.end()) return; mp[ptr] = ++cnt; fa[cnt] = cnt;//初始化 fa[cnt] = findfa(faCnt>0?

faCnt:cnt); RandomListNode *next = ptr->next; RandomListNode *random = ptr->random; it=mp.find(next); if(it==mp.end()){ dfs(next,faCnt>0?faCnt:cnt); } else{ fa[mp[next]] = fa[cnt]; } it=mp.find(random); if(it==mp.end()){ dfs(random,0);//0表示不能确定其父节点 } } //非拓展部分解法 RandomListNode* deepCopy(RandomListNode *head){ //在原链表上双倍复制链表 RandomListNode *ptr1 = head, *ptr2 = NULL; while(ptr1 != NULL){ ptr2 = new RandomListNode(ptr1->label); ptr2->next = ptr1->next; ptr1->next = ptr2; ptr1=ptr2->next; } //复制原链表的random关系 ptr1 = head, ptr2 = NULL; while(ptr1 != NULL){ ptr2 = ptr1->next; if(ptr1->random) ptr2->random = ptr1->random->next; ptr1=ptr2->next; } //将原列表分裂成两个列表 RandomListNode *H =NULL, *ptr3; ptr1 = head, ptr2 = NULL; while(ptr1 != NULL){ ptr2 = ptr1->next; if(H==NULL){ H = ptr2; ptr3 = H; } else{ ptr3->next = ptr2; ptr3 = ptr2; } ptr1->next = ptr2->next; ptr1 = ptr1->next; } return H; } };

你可能感兴趣的文章