Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit49d874a

Browse files
authored
Merge pull requestneetcode-gh#1325 from MHamiid/patch-3
Add 138-Copy-List-with-Random-Pointer.c
2 parents490103a +f1c5eb7 commit49d874a

File tree

1 file changed

+89
-0
lines changed

1 file changed

+89
-0
lines changed

‎c/138-Copy-List-with-Random-Pointer.c

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,89 @@
1+
/**
2+
* Definition for a Node.
3+
* struct Node {
4+
* int val;
5+
* struct Node *next;
6+
* struct Node *random;
7+
* };
8+
*/
9+
10+
/*
11+
Time: O(n)
12+
Space: O(1)
13+
*/
14+
15+
typedefstructNodeNode;
16+
structNode*copyRandomList(structNode*head) {
17+
18+
if(head==NULL)
19+
{
20+
returnNULL;
21+
}
22+
23+
/**
24+
* Insert each new node after each original node
25+
*/
26+
Node*curr=head;
27+
while(curr)
28+
{
29+
// Create the new node
30+
Node*newNode= (Node*)malloc(sizeof(Node));
31+
newNode->val=curr->val;
32+
33+
// Insert new node after the original node
34+
newNode->next=curr->next;
35+
curr->next=newNode;
36+
37+
// Move curr to the next original node
38+
curr=curr->next->next;
39+
}
40+
41+
42+
/**
43+
* Add the random node for each new node
44+
*/
45+
curr=head;
46+
Node*newNode=NULL;
47+
while(curr)
48+
{
49+
// The new node is the next node to the original node
50+
newNode=curr->next;
51+
52+
if(curr->random)
53+
{
54+
newNode->random=curr->random->next;
55+
}
56+
else
57+
{
58+
newNode->random=NULL;
59+
}
60+
61+
// Move curr to the next original node
62+
curr=curr->next->next;
63+
}
64+
65+
/**
66+
* Separate the original nodes list from the new nodes list
67+
*/
68+
Node*originalList=head;
69+
Node*copiedList=head->next;
70+
Node*copiedListHead=head->next;
71+
while(originalList)
72+
{
73+
originalList->next=originalList->next->next;
74+
if(copiedList->next)
75+
{
76+
copiedList->next=copiedList->next->next;
77+
}
78+
else
79+
{
80+
copiedList->next=NULL;
81+
}
82+
83+
originalList=originalList->next;
84+
copiedList=copiedList->next;
85+
}
86+
87+
88+
returncopiedListHead;
89+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp