/* *解题思路: *1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面; *2、重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.random.next; *3、拆分链表,将链表拆分为原链表和复制后的链表 */ public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null) { return null; } RandomListNode currentNode = pHead; //1、复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面; while(currentNode != null){ RandomListNode cloneNode = new RandomListNode(currentNode.label); RandomListNode nextNode = currentNode.next; currentNode.next = cloneNode; cloneNode.next = nextNode; currentNode = nextNode; } currentNode = pHead; //2、重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.random.next; while(currentNode != null) { currentNode.next.random = currentNode.random==null?null:currentNode.random.next; currentNode = currentNode.next.next; } //3、拆分链表,将链表拆分为原链表和复制后的链表 currentNode = pHead; RandomListNode pCloneHead = pHead.next; while(currentNode != null) { RandomListNode cloneNode = currentNode.next; currentNode.next = cloneNode.next; cloneNode.next = cloneNode.next==null?null:cloneNode.next.next; currentNode = currentNode.next; } return pCloneHead; } }
# -*- coding:utf-8 -*- # class RandomListNode: # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution: # 返回 RandomListNode def Clone(self, pHead): if not pHead: return None dummy = pHead # first step, N' to N next while dummy: dummynext = dummy.next copynode = RandomListNode(dummy.label) copynode.next = dummynext dummy.next = copynode dummy = dummynext dummy = pHead # second step, random' to random' while dummy: dummyrandom = dummy.random copynode = dummy.next if dummyrandom: copynode.random = dummyrandom.next dummy = copynode.next # third step, split linked list dummy = pHead copyHead = pHead.next while dummy: copyNode = dummy.next dummynext = copyNode.next dummy.next = dummynext if dummynext: copyNode.next = dummynext.next else: copyNode.next = None dummy = dummynext return copyHead
public class Solution { public RandomListNode Clone(RandomListNode pHead){ if(pHead==null) return null; RandomListNode pCur = pHead; //复制next 如原来是A->B->C 变成A->A'->B->B'->C->C' while(pCur!=null){ RandomListNode node = new RandomListNode(pCur.label); node.next = pCur.next; pCur.next = node; pCur = node.next; } pCur = pHead; //复制random pCur是原来链表的结点 pCur.next是复制pCur的结点 while(pCur!=null){ if(pCur.random!=null) pCur.next.random = pCur.random.next; pCur = pCur.next.next; } RandomListNode head = pHead.next; RandomListNode cur = head; pCur = pHead; //拆分链表 while(pCur!=null){ pCur.next = pCur.next.next; if(cur.next!=null) cur.next = cur.next.next; cur = cur.next; pCur = pCur.next; } return head; } }
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ /*递归思想:把大问题转化若干子问题 此题转化为一个头结点和除去头结点剩余部分,剩余部分操作和原问题一致 */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; //开辟一个新节点 RandomListNode* pClonedHead=new RandomListNode(pHead->label); pClonedHead->next = pHead->next; pClonedHead->random = pHead->random; //递归其他节点 pClonedHead->next=Clone(pHead->next); return pClonedHead; } };
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: //复制原始链表的任一节点N并创建新节点N',再把N'链接到N的后边 void CloneNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; while(pNode!=NULL) { RandomListNode* pCloned=new RandomListNode(0); pCloned->label=pNode->label; pCloned->next=pNode->next; pCloned->random=NULL; pNode->next=pCloned; pNode=pCloned->next; } } //如果原始链表上的节点N的random指向S,则对应的复制节点N'的random指向S的下一个节点S' void ConnectRandomNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; while(pNode!=NULL) { RandomListNode* pCloned=pNode->next; if(pNode->random!=NULL) pCloned->random=pNode->random->next; pNode=pCloned->next; } } //把得到的链表拆成两个链表,奇数位置上的结点组成原始链表,偶数位置上的结点组成复制出来的链表 RandomListNode* ReConnectNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; RandomListNode* pClonedHead=NULL; RandomListNode* pClonedNode=NULL; //初始化 if(pNode!=NULL) { pClonedHead=pClonedNode=pNode->next; pNode->next=pClonedNode->next; pNode=pNode->next; } //循环 while(pNode!=NULL) { pClonedNode->next=pNode->next; pClonedNode=pClonedNode->next; pNode->next=pClonedNode->next; pNode=pNode->next; } return pClonedHead; } //三步合一 RandomListNode* Clone(RandomListNode* pHead) { CloneNodes(pHead); ConnectRandomNodes(pHead); return ReConnectNodes(pHead); } };
3、哈希表法
这个算法写了好久才调出来,指针操作真的很难呀!思想很简单,但是操作起来不简单!!!为方便读者,解析要详细!!!
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; //定义一个哈希表 unordered_multimap<RandomListNode*,RandomListNode*> table; // 开辟一个头结点 RandomListNode* pClonedHead=new RandomListNode(pHead->label); pClonedHead->next=NULL; pClonedHead->random=NULL; // 将头结点放入map中 table.insert(make_pair(pHead,pClonedHead)); //设置操作指针 RandomListNode* pNode=pHead->next; RandomListNode* pClonedNode=pClonedHead; // 第一遍先将简单链表复制一下 while(pNode!=NULL) { // 不断开辟pNode的拷贝结点 RandomListNode* pClonedTail=new RandomListNode(pNode->label); pClonedTail->next=NULL; pClonedTail->random=NULL; //连接新节点,更新当前节点 pClonedNode->next=pClonedTail; pClonedNode=pClonedTail; //将对应关系 插入到哈希表中 table.insert(make_pair(pNode,pClonedTail)); //向后移动操作节点 pNode=pNode->next; } //需从头开始设置random节点,设置操作指针 pNode=pHead; pClonedNode=pClonedHead; // 根据map中保存的数据,找到对应的节点 while(pNode!=NULL) { if(pNode->random!=NULL) { //找到对应节点,更新复制链表 pClonedNode->random=table.find(pNode->random)->second; } //向后移动操作节点 pNode=pNode->next; pClonedNode=pClonedNode->next; } return pClonedHead; } };
/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */ import java.util.HashMap; import java.util.Iterator; import java.util.Map.Entry; import java.util.Set; public class Solution { public RandomListNode Clone(RandomListNode pHead) { HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>(); RandomListNode p = pHead; RandomListNode q = new RandomListNode(-1); while(p!=null){ RandomListNode t = new RandomListNode(p.label); map.put(p, t); p = p.next; q.next = t; q = t; } Set<Entry<RandomListNode,RandomListNode>> set = map.entrySet(); Iterator<Entry<RandomListNode,RandomListNode>> it = set.iterator(); while(it.hasNext()){ Entry<RandomListNode, RandomListNode> next = it.next(); next.getValue().random = map.get(next.getKey().random); } return map.get(pHead); } }
class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; map<RandomListNode*,RandomListNode*> m; RandomListNode* pHead1 = pHead; RandomListNode* pHead2 = new RandomListNode(pHead1->label); RandomListNode* newHead = pHead2; m[pHead1] = pHead2; while(pHead1){ if(pHead1->next) pHead2->next = new RandomListNode(pHead1->next->label); else pHead2->next = NULL; pHead1 = pHead1->next; pHead2 = pHead2->next; m[pHead1] = pHead2; } pHead1 = pHead; pHead2 = newHead; while(pHead1){ pHead2->random = m[pHead1->random]; pHead1 = pHead1->next; pHead2 = pHead2->next; } return newHead; } };
class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; RandomListNode *newHead = new RandomListNode(pHead->label); RandomListNode *pHead1=NULL, *pHead2=NULL; // 上链,使新旧链表成之字形链接 for(pHead1=pHead,pHead2=newHead;pHead1;){ RandomListNode* tmp = pHead1->next; pHead1->next = pHead2; pHead2->next = tmp; // next pHead1 = tmp; if(tmp) pHead2 = new RandomListNode(tmp->label); else pHead2 = NULL; } // 更新新链表的random指针 for(pHead1=pHead,pHead2=newHead;pHead1;){ if(pHead1->random) pHead2->random = pHead1->random->next; else pHead2->random = NULL; pHead1 = pHead2->next; if(pHead1) pHead2 = pHead1->next; else pHead2 = NULL; } // 脱链,更新各链表的next指针 for(pHead1=pHead,pHead2=newHead;pHead1;){ pHead1->next = pHead2->next; if(pHead1->next) pHead2->next = pHead1->next->next; else pHead2->next = NULL; pHead1 = pHead1->next; pHead2 = pHead2->next; } return newHead; } };
import java.util.HashMap; public class Solution { public RandomListNode Clone(RandomListNode pHead) { HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>(); RandomListNode cur = pHead; while (cur != null) { map.put(cur, new RandomListNode(cur.label)); cur = cur.next; } cur = pHead; while (cur != null) { map.get(cur).next = map.get(cur.next); cur = cur.next; } RandomListNode resHead = map.get(pHead); cur = pHead; while (cur != null) { map.get(cur).random = map.get(cur.random); cur = cur.next; } return resHead; } }
class Solution:
def Clone(self, head):
if not head: return
newNode = RandomListNode(head.label)
newNode.random = head.random
newNode.next = self.Clone(head.next)
return newNode
class Solution:
def Clone(self, head):
nodeList = [] #存放各个节点
randomList = [] #存放各个节点指向的random节点。没有则为None
labelList = [] #存放各个节点的值
while head:
randomList.append(head.random)
nodeList.append(head)
labelList.append(head.label)
head = head.next
#random节点的索引,如果没有则为1
labelIndexList = map(lambda c: nodeList.index(c) if c else -1, randomList)
dummy = RandomListNode(0)
pre = dummy
#节点列表,只要把这些节点的random设置好,顺序串起来就ok了。
nodeList=map(lambda c:RandomListNode(c),labelList)
#把每个节点的random绑定好,根据对应的index来绑定
for i in range(len(nodeList)):
if labelIndexList[i]!=-1:
nodeList[i].random=nodeList[labelIndexList[i]]
for i in nodeList:
pre.next=i
pre=pre.next
return dummy.next
class Solution { map<RandomListNode*, RandomListNode*> mp; set<RandomListNode*> vis; void dfs1(RandomListNode* u){ if(u && mp.find(u) == mp.end()) { mp[u] = new RandomListNode(u -> label); dfs1(u -> next); dfs1(u -> random); } } void dfs2(RandomListNode* u){ if(u && vis.find(u) == vis.end()){ if(u -> next) mp[u] -> next = mp[u -> next]; if(u -> random) mp[u] -> random = mp[u -> random]; vis.insert(u); dfs2(u -> next); dfs2(u -> random); } } public: RandomListNode* Clone(RandomListNode* pHead){ if(!pHead) return NULL; mp.clear(); vis.clear(); dfs1(pHead); dfs2(pHead); return mp[pHead]; } };
class Solution { public: /* 1、复制每个节点,如:复制节点A得到A1,将A1插入节点A后面 2、遍历链表,A1->random = A->random->next; 3、将链表拆分成原链表和复制后的链表 */ RandomListNode* Clone(RandomListNode* pHead) { if(!pHead) return NULL; RandomListNode *currNode = pHead; while(currNode){ RandomListNode *node = new RandomListNode(currNode->label); node->next = currNode->next; currNode->next = node; currNode = node->next; } currNode = pHead; while(currNode){ RandomListNode *node = currNode->next; if(currNode->random){ node->random = currNode->random->next; } currNode = node->next; } //拆分 RandomListNode *pCloneHead = pHead->next; RandomListNode *tmp; currNode = pHead; while(currNode->next){ tmp = currNode->next; currNode->next =tmp->next; currNode = tmp; } return pCloneHead; } };
public class Solution { public RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return null; RandomListNode newNode = new RandomListNode(pHead.label); newNode.random = pHead.random; newNode.next = Clone(pHead.next); return newNode; } }
public class Solution { public RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return null; RandomListNode pCur = pHead; while (pCur != null) { RandomListNode node = new RandomListNode(pCur.label); node.next = pCur.next; pCur.next = node; pCur = node.next; } pCur = pHead; while (pCur!=null) { if (pCur.random!=null) pCur.next.random = pCur.random.next; pCur = pCur.next.next; } RandomListNode head = pHead.next; RandomListNode tmp = head; pCur = pHead; while(pCur.next!=null) { tmp = pCur.next; pCur.next = tmp.next; pCur = tmp; } return head; } }
/*public class RandomListNode {int label;RandomListNode next = null;RandomListNode random = null;RandomListNode(int label) {this.label = label;}}*/importjava.util.HashMap;publicclassSolution {publicRandomListNode Clone(RandomListNode pHead){if(pHead == null) returnnull;HashMap<RandomListNode, RandomListNode> map = newHashMap<RandomListNode, RandomListNode>();RandomListNode newHead = newRandomListNode(pHead.label);RandomListNode pre = pHead, newPre = newHead;map.put(pre, newPre);while(pre.next != null){newPre.next = newRandomListNode(pre.next.label);pre = pre.next;newPre = newPre.next;map.put(pre, newPre);}pre = pHead;newPre = newHead;while(newPre != null){newPre.random = map.get(pre.random);pre = pre.next;newPre = newPre.next;}returnnewHead;}}
public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null) return null; RandomListNode node = pHead; //复制节点,并放在源节点之后 while(node != null ){ RandomListNode newNode = new RandomListNode(node.label); newNode.label = node.label; newNode.next = node.next; newNode.random = null; node.next = newNode; node = newNode.next; } //复制random指向复制后的节点 node = pHead; while(node != null){ RandomListNode newNode = node.next; if(node.random != null){ newNode.random = node.random.next; } node = newNode.next; } //获取新的链表 RandomListNode newHead = null; RandomListNode cloneNode = null; RandomListNode pNode = pHead; if(pNode != null){ newHead = pNode.next; cloneNode = pNode.next; pNode.next = cloneNode.next; pNode = pNode.next; } while(pNode != null){ cloneNode.next = pNode.next; cloneNode = cloneNode.next; pNode.next = cloneNode.next; pNode = pNode.next; } return newHead; } }
//C++实现 时间效率O(n) 空间效率为0 最优解法 /* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { CloneNodes(pHead); ConnectRandomNodes(pHead); return Distract(pHead); } //把每一个节点的复制后的节点,连接在每一个后面 void CloneNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; while(pNode!=nullptr) { //构造函数,新开辟空间用于存复制的节点,由于后面没有赋节点给pCloneNode的步骤,所以不能赋值为nullptr RandomListNode* pCloneNode=new RandomListNode(0);//label初始化为0 pCloneNode->label=pNode->label;//此步复制了节点 pCloneNode->next=pNode->next; pCloneNode->random=nullptr; pNode->next=pCloneNode; pNode=pCloneNode->next; } } //设置复制出来的节点的random指针 void ConnectRandomNodes(RandomListNode* pHead) { RandomListNode* pNode=pHead; while(pNode!=nullptr) { RandomListNode* pCloneNode=pNode->next; if(pNode->random!=nullptr) pCloneNode->random=pNode->random->next; pNode=pCloneNode->next; } } //将一个链表拆分为两个链表,并只返回复制的那个链表 RandomListNode* Distract(RandomListNode* pHead) { RandomListNode* pNode=pHead;//把A赋给pNode RandomListNode* pCloneHead=nullptr; RandomListNode* pCloneNode=nullptr; if(pNode!=nullptr) { pCloneNode=pNode->next; pCloneHead=pNode->next; pNode->next=pCloneNode->next;//A->B连接 pNode=pCloneNode->next;//把B赋给pNode } while(pNode!=nullptr) { pCloneNode->next=pNode->next;//A'->B'连接 pCloneNode=pNode->next;//把B‘赋给pCloneNode pNode->next=pCloneNode->next;//B->C连接 等 pNode=pCloneNode->next;//把C赋给pNode 等 } return pCloneHead; } };
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; RandomListNode* curNode = pHead; while(curNode!=NULL){ RandomListNode* newNode = new RandomListNode(curNode->label); newNode->next = curNode->next; curNode->next = newNode; curNode = newNode->next; } curNode = pHead; while(curNode!=NULL){ if(curNode->random!=NULL) curNode->next->random = curNode->random->next; curNode = curNode->next->next; } RandomListNode* head = pHead->next; curNode = pHead; while(curNode->next!=NULL){ RandomListNode* pNext = curNode->next; curNode->next = pNext->next; curNode = pNext; } return head; } };
//利用C++中的map,虽然空间效率有浪费 //思路简单 class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead == NULL) return NULL; RandomListNode* p1 =new RandomListNode(pHead->label); RandomListNode* pNewHead = p1; RandomListNode* p2 = pHead; while(p2->next){ p1->next = new RandomListNode(p2->next->label); p2 = p2->next; p1 = p1->next; } map<RandomListNode *, RandomListNode *> my_Map; my_Map[NULL] = NULL; p1 = pNewHead; p2 = pHead; while(p1 && p2){ my_Map[p2] = p1; p1 = p1->next; p2 = p2->next; } p1 = pNewHead; p2= pHead; while(p1 && p2){ p1->random = my_Map[p2->random]; p1 = p1->next; p2 = p2->next; } return pNewHead; } };
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { if(pHead==NULL) return NULL; RandomListNode* current = pHead; while(current!=NULL){ RandomListNode* node = new RandomListNode(current->label); node->next = current->next; current->next = node; current = node->next;//处理下一个节点 } //处理random指针 current = pHead; while(current!=NULL){ if(current->random!=NULL) current->next->random = current->random->next; current = current->next->next; } //生成复制链表 RandomListNode *temp,*pNewHead; pNewHead = pHead->next; current = pHead; temp = pNewHead; while(current!=NULL){ current->next = current->next->next; if(temp->next!=NULL) temp->next = temp->next->next; temp = temp->next; current = current->next; } return pNewHead; } };
public RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return null; RandomListNode t = pHead; while (t != null) { RandomListNode p = t.next; RandomListNode r = new RandomListNode(t.label); // copy next t.next = r; r.next = p; t = p; } t = pHead; RandomListNode r = t.next; while (t != null) { if (t.random != null) r.random = t.random.next;// copy random t = r.next; if (t == null) break; r = t.next; } t = pHead; r = t.next; RandomListNode cHead = r; // copy head while (t != null) { t.next = r.next; t = r.next; if (t == null) break; r.next = t.next; r = t.next; } return cHead; }
public RandomListNode Clone(RandomListNode pHead) { if (pHead == null) return pHead; RandomListNode pNode = pHead; while (pNode != null) { int val = pNode.label; RandomListNode randomListNode = new RandomListNode(val); randomListNode.next = pNode.next; pNode.next = randomListNode; pNode = randomListNode.next; } pNode = pHead; while (pNode != null) { RandomListNode next = pNode.next; RandomListNode random = pNode.random; if (random != null) next.random = random.next; pNode = next.next; } pNode = pHead; RandomListNode second = pHead.next; while (pNode != null) { RandomListNode next = pNode.next; pNode.next = next.next; pNode = next.next; if (pNode != null) next.next = pNode.next; } return second; }