Copy List with Random Pointer

文章目录

1. Copy List with Random Pointer

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.

思路

原始链表

新建链表

新建链表划分

解题

/**
 * 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) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        for (RandomListNode* cur = head; cur != nullptr; ) {
            RandomListNode* node = new RandomListNode(cur->label);
            node->next = cur->next;
            cur->next = node;
            cur = node->next;
        }
        for (RandomListNode* cur = head; cur != nullptr; ) {
            if (cur->random != NULL)
            cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        RandomListNode dummy(-1);
        for (RandomListNode* cur = head, *new_cur = &dummy;
        cur != nullptr; ) {
        new_cur->next = cur->next;
        new_cur = new_cur->next;
        cur->next = cur->next->next;
        cur = cur->next;
        }
        return dummy.next;
    }
};

python版

# Definition for singly-linked list with a random pointer.
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution:
    # @param head, a RandomListNode
    # @return a RandomListNode
    def copyRandomList(self, head):
        cur=head
        while(cur):
            node=RandomListNode(cur.label)
            node.next=cur.next
            cur.next=node
            cur=node.next
        cur=head
        while(cur):
            if(cur.random!=None):
                cur.next.random=cur.random.next
            cur=cur.next.next
        dummy=RandomListNode(0)
        new_cur=dummy
        cur=head
        while(cur):
           new_cur.next=cur.next
           new_cur=cur.next
           cur.next=cur.next.next
           cur=cur.next
        return dummy.next