单页设计网站,做外包网站的公司是怎样的,wordpress注册无效,抛丸机网站排名优化例题解析
138. 随机链表的复制 - 力扣#xff08;LeetCode#xff09; 1.拷贝节点插入原节点的后面#xff08;核心#xff09;
这样做的目的是方便找 random 节点#xff0c;知道原节点可以找 random#xff0c;知道上一个 random 可以找下一个 random 。 struct Node… 例题解析
138. 随机链表的复制 - 力扣LeetCode 1.拷贝节点插入原节点的后面核心
这样做的目的是方便找 random 节点知道原节点可以找 random知道上一个 random 可以找下一个 random 。 struct Node* curhead;while(cur){//通过一前一后两个指针来插入节点struct Node* nextcur-next;struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;//链接cur-nextcopy;copy-nextnext;//cur移动curnext;}
2.放置每个拷贝节点的 random
我们可以通过原节点的 random 轻松找到拷贝的 random curhead;//放置拷贝节点的randomwhile(cur){//从cur的下一个节点开始遍历struct Node* copycur-next;//如果原节点的random为空拷贝节点的random也为空if(cur-randomNULL){copy-randomNULL;}else//否则拷贝节点的random等于原节点的random的拷贝节点{copy-randomcur-random-next;}//cur后移动一位curcopy-next;}
3.将拷贝节点与原链表解开尾插到一起并恢复原链表的链接 curhead;
//创建新链表的头尾节点便于插入struct Node* copyheadNULL,*copytailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;//copy节点尾插到新链表if(copyheadNULL){copy copyheadcopytail;}else{copytail-nextcopy;copytailcopytail-next;}//恢复原节点cur-nextnext;curnext;}
完整代码
/*** Definition for a Node.* struct Node {* int val;* struct Node *next;* struct Node *random;* };*/struct Node* copyRandomList(struct Node* head) {//拷贝节点到原节点的后面struct Node* curhead;while(cur){//通过一前一后两个指针来插入节点struct Node* nextcur-next;struct Node* copy(struct Node*)malloc(sizeof(struct Node));copy-valcur-val;//链接cur-nextcopy;copy-nextnext;//cur移动curnext;}curhead;//放置拷贝节点的randomwhile(cur){//从cur的下一个节点开始遍历struct Node* copycur-next;//如果原节点的random为空拷贝节点的random也为空if(cur-randomNULL){copy-randomNULL;}else//否则拷贝节点的random等于原节点的random的拷贝节点{copy-randomcur-random-next;}//cur后移动一位curcopy-next;}curhead;//创建新链表的头尾节点便于插入struct Node* copyheadNULL,*copytailNULL;while(cur){struct Node* copycur-next;struct Node* nextcopy-next;//copy节点尾插到新链表if(copytailNULL){copyheadcopytailcopy;}else{copytail-nextcopy;copytailcopytail-next;}//恢复原节点cur-nextnext;curnext;}return copyhead;
} 4.顺序表和链表的区别 拓展学习
