力扣 138. 随机链表的复制

1.解题思路

在原先链表的每一个元素后面插入一个与前一个相同val的值的结点,然后由于是在原链表进行的操作，因此找每个random就变得很方便直接访问即可，此题目的精髓是cur1->random=p->random->next,看懂这串代码的话，这道题也就迎刃而解了.

2.代码实现

struct Node* copyRandomList(struct Node* head)
 { 
  struct Node* cur=head;
   while(cur)
   {   struct Node* next=cur->next;
       struct Node*p=( struct Node*)malloc(sizeof( struct Node));
       p->val=cur->val;
       p->next=next;
       cur->next=p;
       cur=next;
   }
 struct Node* p=head;
 while(p)
 { 
   struct Node* cur1=p->next;
   if(p->random==NULL)
   {
       cur1->random=NULL;
       p=cur1->next;
   }
else
{
   cur1->random=p->random->next;
   p=cur1->next;
}

 }
 struct Node*newnode=NULL;
   struct Node*tail=NULL;
 while(head)
 {
  if(tail==NULL)
  {
    tail=newnode=head->next;
    head=head->next->next;
  }
  else
  {
     tail->next=head->next;
     tail=head->next;
     head=head->next->next;
  }

 }
return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

结尾：今天的分享到此结束，喜欢的朋友如果感觉有帮助可以点赞三连支持，咱们共同进步!