链表的深拷贝问题

deepCopyList.md

一个链表有一个int数据域，一个next指针域，一个random指针域，random要么指向一个随机的node，要么置空，对此链表进行深拷贝

	/**
	 * Definition for singly-linked list with a random pointer.
	 * struct RandomListNode {
	 *     int label;
	 *     RandomListNode *next, *random;
	 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
	 * };
	 */

思路

将新的节点插入到原始节点的后面，然后找到random节点，最后分拆连个链表

	class Solution {
	public:
	    RandomListNode *copyRandomList(RandomListNode *head) {
	        if(!head){
	            return nullptr;
	        }
	        /*
	        add new node after the old one
	        */
	        for(auto cur = head;cur != nullptr;){
	            RandomListNode* p =  new RandomListNode(cur->label);
	            p->next = cur->next;
	            cur->next = p;
	            cur = p->next;
	        }
	        /*
	        find random node
	        */
	        for(auto cur = head;cur != nullptr;){
	            if(cur->random != nullptr){
	                cur->next->random = cur->random->next;
	            }
	            cur = cur->next->next;
	        }
	        /*
	        split two list
	        */
	        RandomListNode* newHead = new RandomListNode(-1);
	        for(auto cur = head,newCur = newHead;cur != nullptr;){
	            newCur->next = cur->next;
	            newCur = newCur->next;
	            cur->next = cur->next->next;
	            cur = cur->next;
	        }
	        return newHead->next;
	    }
	};