# 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.

分析

直接遍历链表，遇到需要的就创建或者返回，用MAP记录NODE： old node: new node

```
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""


class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return
        map = {}
        def getnode(cur):
            if cur not in map:
                map[cur] = Node(cur.val)
            return map[cur]
            
        cur = head
        while cur:
            node = getnode(cur)
            if cur.next:
                node.next = getnode(cur.next)
            if cur.random:
                node.random = getnode(cur.random)
            cur = cur.next
        return getnode(head)

```

2个loop，第一个复制新Node插入旧node后面。第二次设置新建Node们的random指针。最后split2个链表

```
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode dummy = new RandomListNode(0);
        dummy.next = head;
        RandomListNode cur = head;
        while(cur != null){
            RandomListNode node = new RandomListNode(cur.label);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        while(cur != null){
            if(cur.random != null)//这个不能放在while判断里
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        //split
        RandomListNode nh = new RandomListNode(0);
        cur = nh;
        //next 一步步的走，不要next.next的跳
        //先设置好next，然后再跳向next。
        while(head != null){
            nh.next = head.next;  
            nh = nh.next;
            head.next = nh.next;            
            head = head.next;
        }
        return cur.next;
    }
}
```

可以用Map，就是耗空间。用原地copy省空间 No extra space

这里cur=head，用cur走

最后split，cur=dummy=nhead

最后split用cur.next.next一直出错 以后尽量不用.next.next

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

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        if not head:
            return head

        cur = head

        while cur:
            copied = RandomListNode(cur.label)
            copied.next = cur.next
            cur.next = copied
            cur = cur.next.next

        cur = head

        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        nhead = RandomListNode(-1)
        cur = nhead
        while head:
            nhead.next = head.next
            nhead = nhead.next
            head.next = nhead.next
            head = head.next


        return cur.next
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/l6lian-biao/copy-list-with-random-pointer.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.