LeetCode 138. Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

	/*
	// Definition for a Node.
	class Node {
	public:
	int val;
	Node* next;
	Node* random;
	Node(int _val) {
	val = _val;
	next = NULL;
	random = NULL;
	}
	};
	*/
	class Solution {
	public:
	Node* copyRandomList(Node* head) {
	Node* null_ptr = NULL;
	if(!head) return null_ptr;
	auto org_head = head;
	// interweave: a->a1->b->b1->c->c1
	while(head){
	// a -> a1 -> b
	auto n = new Node(head->val);
	if(head->next) n->next = head->next;
	head->next = n;
	// iterate
	head = n->next;
	}
	// set random
	head = org_head;
	while(head){
	if(head->random) head->next->random = head->random->next;
	head = head->next->next;
	}
	// restore org & new head
	auto copy = new Node(0);
	auto c = copy;
	head = org_head;
	while(head){
	c->next = head->next;
	head->next = head->next->next;
	// iterate
	c = c->next;
	head = head->next;
	}
	return copy->next;
	}
	};

view raw 138-Copy-List-with-Random-Pointer.cpp hosted with ❤ by GitHub