首页 > 代码库 > 25、剑指offer--复杂链表的复制

25、剑指offer--复杂链表的复制

2024-09-26 21:58:39   215人阅读

题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 
思路：直接把复制的node放在原node的后面，这样结构变为：
技术分享
上面为第一次遍历，第二次遍历时把红色的新node的random域赋值，规则是：
newNode->ranodm = oldNode->random->next;
然后第三次遍历把上面的链表拆分为两个即可。代码如下：
 
 1 /**
 2  * Definition for singly-linked list with a random pointer.
 3  * struct RandomListNode {
 4  *     int label;
 5  *     RandomListNode *next, *random;
 6  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     RandomListNode *copyRandomList(RandomListNode *head) {
12         RandomListNode *newList = NULL;
13         RandomListNode *newHead = NULL;
14         RandomListNode *p = head;
15  
16         if(head==NULL)
17             return NULL;
18         //把每一个新的结点放入旧结点后面
19         while(p!=NULL)
20         {
21             RandomListNode *q = new RandomListNode(p->label);
22             q->next = p->next;
23             p->next = q;
24  
25             p = q->next;
26         }
27  
28         p = head;
29         //在新结点中加入random
30         while(p!=NULL)
31         {
32             if(p->random != NULL)
33                 p->next->random = p->random->next;
34             p = p->next->next;//此时p需要跳两步才到旧的下一节点
35         }
36         p = head;
37         //注意这里的条件，首先要判断p是否为null
38         while(p!=NULL && p->next!=NULL)
39         {
40             if(p==head)
41             {
42                 newHead = p->next;
43                 newList = newHead;
44             }
45             else
46             {
47                 newList->next = p->next;
48                 newList = newList->next;
49             }
50             
51             
52              p->next = newList->next;  
53              p = p->next;
54              //如果使用p = newList->next;替换以上两步，则会改变原链表，错误
55  
56         }
57  
58         return newHead;//返回值是newHead而不是newList，因为此时newList指向尾部
59     }
60 };

 

 

 

25、剑指offer--复杂链表的复制


联系
我们