首页 > 代码库 > [leetCode] Copy List with Random Pointer
[leetCode] Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
思路：首先将新节点连接到所复制的节点后面，再这样的链表上处理random指针。
时间复杂度O(n),空间复杂度O(1)
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 if (head == NULL) return head;13 14 15 for (RandomListNode *curr = head; curr != NULL;) {16 RandomListNode *pter = new RandomListNode(curr->label);17 pter->next = curr->next;18 curr->next = pter;19 curr = pter->next;20 }21 22 //链接rando指针23 for(RandomListNode *curr = head; curr != NULL;) {24 if (curr->random != NULL) {25 curr->next->random = curr->random->next;26 }27 curr = curr->next->next;28 }29 30 //分拆链表31 RandomListNode *new_head = head->next;32 for (RandomListNode *curr = head, **new_curr = &new_head; curr != NULL;) {33 *new_curr = curr->next;34 curr->next = curr->next->next;35 36 curr = curr->next;37 38 new_curr = &((*new_curr)->next);39 }40 41 return new_head;42 }43 };
[leetCode] Copy List with Random Pointer
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。