leetcode138复制带随机指针的链表

一时失言乱红尘 2023-06-22 05:30 8阅读 0赞

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。

示例：  
![在这里插入图片描述][format_png]

输入：  
\{“KaTeX parse error: Expected '\}', got 'EOF' at end of input: …":"1","next":\{"id”:“2”,“next”:null,“random”:\{“KaTeX parse error: Expected 'EOF', got '\}' at position 9: ref":"2"\}̲,"val":2\},"rand…ref”:“2”\},“val”:1\}

解释：  
节点 1 的值是 1，它的下一个指针和随机指针都指向节点 2 。  
节点 2 的值是 2，它的下一个指针指向 null，随机指针指向它自己。

提示：

你必须返回给定头的拷贝作为对克隆列表的引用。

思路： 遍历当前节点，复制当前节点，第二次遍历时，处理next,random指针。

思路1

public Node copyRandomList(Node head) {
        
            if (head == null )  return head;
            Node node = head;
            Map<Node,Node> map = new HashMap<>();
            while (node != null) {
        
                Node clone = new Node(node.val,null,null);
                map.put(node,clone);
                node = node.next;
            }
    
            node = head;
            while (node != null) {
        
                Node clone = map.get(node);
                clone.next = map.get(node.next);
                clone.random = map.get(node.random);
                node = node.next;
            }
            return map.get(head);
        }

思路二： 先保存当前节点的复制节点接在链表后面，再处理random，最后分开2条链表。

/*
    // Definition for a Node.
    class Node {
        public int val;
        public Node next;
        public Node random;
    
        public Node() {}
    
        public Node(int _val,Node _next,Node _random) {
            val = _val;
            next = _next;
            random = _random;
        }
    };
    */
    class Solution {
        
        public Node copyRandomList(Node head) {
        
            if (head == null )  return head;
            Node node = head;
            while (node != null) {
        
                Node t = new Node();
                t.val = node.val;
                t.next = node.next;
                node.next = t;
                node = node.next.next;
            }
    
            node = head;
            while (node != null) {
        
                if (node.random != null) {
        
                    Node t = node.next;
                    if (t != null) {
        
                        t.random = node.random.next;
                    }
                }
                node = node.next.next;
            }
    
            node = head;
            Node l2_head = head.next;
            Node l2 = null;
            while (node != null) {
        
                l2 = node.next;             先保存主节点
                node.next = l2.next;        遍历节点连接下一个遍历点
                if (l2.next != null) {
        
                    l2.next = l2.next.next;  主节点连接下一个主节点
                }
                node = node.next;            遍历节点移动
            }
            return l2_head;
        }
    }

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9hc3NldHMubGVldGNvZGUtY24uY29tL2FsaXl1bi1sYy11cGxvYWQvdXBsb2Fkcy8yMDE5LzAyLzIzLzE0NzAxNTA5MDYxNTMtMnl4ZXpubS5wbmc?x-oss-process=image/format,png