Title Description

Enter a complex linked list (each node has node values, and two pointers, one to the next node, and the other special pointer to any node), and the return result is the head of the copied complex linked list. (Note: please do not return the node reference in the parameter in the output result, otherwise the problem determination program will directly return null)
 

Ideas: (three steps)

1. Link the copied node behind each corresponding node of the original linked list

2. Point the random pointer of the copied node to the next node of the random pointer of the copied node

3. Split it into two linked lists. The odd position is the original linked list, and the even position is the duplicate linked list. Note that the next pointer of the last node of the duplicate linked list cannot point to the same null node None as the original linked list. The next pointer should be reassigned to None (the judgment program will determine that you have not finished copying)

/*
*Solutions:
*1,Traverse the list and copy each node. For example, copy node a to get A1, and insert node A1 after node a;
*2,Traverse the linked list again, copy the random pointer of the old node to the new node, such as A1.random = A.random.next;
*3,Split the linked list into the original one and the copied one
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }
         
        RandomListNode currentNode = pHead;
        //1. Copy each node, for example, copy node a to get A1, and insert node A1 after node a;
        while(currentNode != null){
            RandomListNode cloneNode = new RandomListNode(currentNode.label);
            RandomListNode nextNode = currentNode.next;
            currentNode.next = cloneNode;
            cloneNode.next = nextNode;
            currentNode = nextNode;
        }
         
        currentNode = pHead;
        //2. Traverse the linked list again, copy the random pointer of the old node to the new node, such as A1.random = A.random.next;
        while(currentNode != null) {
            currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
            currentNode = currentNode.next.next;
        }
         
        //3. Split the linked list into the original one and the copied one
        currentNode = pHead;
        RandomListNode pCloneHead = pHead.next;
        while(currentNode != null) {
            RandomListNode cloneNode = currentNode.next;
            currentNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            currentNode = currentNode.next;
        }
         
        return pCloneHead;
    }
}

map hash table method:

/utilize C++Medium map,Although space efficiency is wasteful
//Simple thinking
class Solution {
public:
    RandomListNode* Clone(RandomListNode* pHead)
    {
        if(pHead == NULL) return NULL;
        RandomListNode* p1 =new RandomListNode(pHead->label);
        RandomListNode* pNewHead = p1;
        RandomListNode* p2 = pHead;
         
        while(p2->next){
            p1->next = new RandomListNode(p2->next->label); //I think this way is to copy a node with only value but no backward pointer, and the pointer is determined by us later, so as not to copy the original node with pointer and disconnect it
            p2 = p2->next; p1 = p1->next;
        }
         
        map<RandomListNode *, RandomListNode *>  my_Map; 
        my_Map[NULL] = NULL;
        p1 = pNewHead;
        p2 = pHead;
        while(p1 && p2){   //Building tables
            my_Map[p2] = p1;
            p1 = p1->next; p2 = p2->next;
        }
         
        p1 = pNewHead;
        p2= pHead;
        while(p1 && p2){
            p1->random = my_Map[p2->random];  //Look-up table
            p1 = p1->next; p2 = p2->next;
        }
         
        return pNewHead;
    }
};

map correlation:

First, traverse the original linked list once, create a new linked list (assign label and next), associate the corresponding node with map; then traverse again, update the random pointer of the new linked list. (note that there should be a null - > null mapping in the map)