Clean C++ O(1) space solution, the idea is the same as others but it's clean and pure!


  • 6
    P
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *node = head, *nextNode;
        while (node) {
            nextNode = node->next;
            node->next = new RandomListNode(node->label);
            node->next->next = nextNode;
            node = nextNode;
        }
        node = head;
        while (node) {
            node->next->random = node->random ? node->random->next : nullptr;
            node = node->next->next;
        }
        RandomListNode *psuedoHead = new RandomListNode(0), *copyNode = psuedoHead;
        node = head;
        while (node) {
            copyNode->next = node->next;
            copyNode = node->next;
            node->next = node->next->next;
            node = node->next;
        }
        return psuedoHead->next;
    }

  • 0
    M

    Great idea!!!
    Append all new node behind the old node, so we can easily find the new random node by the old random node.

    Besides: the psuedoHead seems to be leaked, need to destroy before return.


  • 0
    C

    I'd appreciate it if you could explain your code for me!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.