[剑指offer]面试题第[35]题[Leetcode][第138题][JAVA][复杂链表的复制][暴力][HashMap][复制链表]

╰半夏微凉° 2023-03-01 09:05 6阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 暴力 直接复制 ######

将链表从头节点一个一个复制下去，  
在根据记录的总长度num，遍历原来的每个节点的random到尾节点个数count，然后顺序遍历找到新链表的该指针在num-count上 。  
**时间复杂度：O(N^2) 空间复杂度：O(N)**

class Solution { 
       public Node copyRandomList(Node head) { 
            if(head==null) return head;
            Node newHead=new Node(head.val);
            Node keep=newHead;
            Node node=head.next;
            int num=1;//记录节点数
            while(node!=null){ 
                keep.next=new Node(node.val);
                node=node.next;
                keep=keep.next;
                num++;
            }
            keep.next=null;
            Node newn=newHead;
            Node oldn=head;
            //n r 定位random
            Node n;
            Node r;
            int count;
            while (oldn!=null){ 
                n= oldn.random;//进行循环找到酒链表random指向的位置n
                r=newHead;
                count=0;//计算出旧链表n距离尾节点个数
                while (n!=null){ 
                    n=n.next;
                    count++;
                }
                //计算旧的random在链表中的位置 利用新旧链表新旧位置相同的原理
                for(int res=num-count;res>0;res--){ 
                    r=r.next;
                }
                newn.random=r;
                //遍历新旧链表
                oldn=oldn.next;
                newn=newn.next;
            }
            return newHead;
        }
    }
    
    作者：zhao-1z
    链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/javaliang-chong-xie-fa-by-zhao-1z/

###### 2. HashMap O(N)空间 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

\*\*时间复杂度：O(N) 空间复杂度：O(N) \*\*  
![在这里插入图片描述][20200723113046371.png]

/* // 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; } }; */
    public class Solution { 
      // Visited dictionary to hold old node reference as "key" and new node reference as the "value"
      HashMap<Node, Node> visited = new HashMap<Node, Node>();
    
      public Node getClonedNode(Node node) { 
        // If the node exists then
        if (node != null) { 
          // Check if the node is in the visited dictionary
          if (this.visited.containsKey(node)) { 
            // If its in the visited dictionary then return the new node reference from the dictionary
            return this.visited.get(node);
          } else { 
            // Otherwise create a new node, add to the dictionary and return it
            this.visited.put(node, new Node(node.val, null, null));
            return this.visited.get(node);
          }
        }
        return null;
      }
    
      public Node copyRandomList(Node head) { 
    
        if (head == null) { 
          return null;
        }
    
        Node oldNode = head;
    
        // Creating the new head node.
        Node newNode = new Node(oldNode.val);
        this.visited.put(oldNode, newNode);
    
        // Iterate on the linked list until all nodes are cloned.
        while (oldNode != null) { 
          // Get the clones of the nodes referenced by random and next pointers.
          newNode.random = this.getClonedNode(oldNode.random);
          newNode.next = this.getClonedNode(oldNode.next);
    
          // Move one step ahead in the linked list.
          oldNode = oldNode.next;
          newNode = newNode.next;
        }
        return this.visited.get(head);
      }
    }
    
    作者：LeetCode
    链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/fu-zhi-dai-sui-ji-zhi-zhen-de-lian-biao-by-leetcod/

###### 3. HashMap O(N)空间 ######

遍历第一遍链表，我们不考虑链表之间的相互关系，仅仅生成所有节点，然后把它存到 HashMap 中，h（val） 作为 key，Node 作为 value。

遍历第二遍链表，将之前生成的节点取出来，更新它们的 next 和 random 指针。

**时间复杂度：O(N) 空间复杂度：O(N)**

public Node copyRandomList(Node head) { 
        if (head == null) { 
            return null;
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node h = head;
        while (h != null) { 
            Node t = new Node(h.val); 
            map.put(h, t);
            h = h.next;
        }
        h = head;
        while (h != null) { 
            if (h.next != null) { 
                map.get(h).next = map.get(h.next);
            }
            if (h.random != null) { 
                map.get(h).random = map.get(h.random);
            }
            h = h.next;
        }
        return map.get(head);
    }
    
    作者：windliang
    链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-32/

###### 4. HashMap O(N)空间 ######

只遍历一次链表。  
核心思想就是延迟更新它的 next。

> 1 -> 2 -> 3  
> 用 cur 指向已经生成的节点的末尾  
> 1 -> 2  
> ^  
> c  
> 然后将 3 构造完成  
> 最后将 2 的 next 指向 3  
> 1 -> 2 -> 3  
> ^  
> c  
> 期间已经生成的节点存到 HashMap 中，第二次遇到的时候直接从 HashMap 中拿

**时间复杂度：O(N) 空间复杂度：O(N)**

public Node copyRandomList(Node head) { 
        if (head == null) { 
            return null;
        }
        HashMap<Node, Node> map = new HashMap<>();
        Node h = head;
        Node cur = new Node(-1); //空结点，dummy 节点，为了方便头结点计算
        while (h != null) { 
            //判断当前节点是否已经产生过
            if (!map.containsKey(h)) { 
                Node t = new Node(h.val);
                map.put(h, t);
            }
            //得到当前节点去更新它的 random 指针
            Node next = map.get(h);
            if (h.random != null) { 
                //判断当前节点是否已经产生过
                if (!map.containsKey(h.random)) { 
                    next.random = new Node(h.random.val);
                    map.put(h.random, next.random);
                } else { 
                    next.random = map.get(h.random);
                }
    
            }
            //将当前生成的节点接到 cur 的后边
            cur.next = next;
            cur = cur.next;
            h = h.next;
        }
        return map.get(head);
    }

###### 5. O(1)空间 (用原链表的 next 域保存新生成的节点) ######

主要解决的问题就是我们生成节点以后，当更新它的 random 的时候，怎么找到之前生成的节点，前两种解法用了 HashMap 全部存起来，这里的话可以利用原来的链表的指针域。

主要需要三步。

1.  生成所有的节点，并且分别插入到原有节点的后边
2.  更新插入节点的 random
3.  将新旧节点分离开来  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]

**时间复杂度：O(N) 空间复杂度：O(1)**

public Node copyRandomList(Node head) { 
        if (head == null) { 
            return null;
        }
        Node l1 = head;
        Node l2 = null;
        //生成所有的节点，并且分别插入到原有节点的后边
        while (l1 != null) { 
            l2 = new Node(l1.val);
            l2.next = l1.next;
            l1.next = l2;
            l1 = l1.next.next;
        }
        //更新插入节点的 random
        l1 = head;
        while (l1 != null) { 
            if (l1.random != null) { 
                l1.next.random = l1.random.next;
            }
            l1 = l1.next.next;
        }
    
        l1 = head;
        Node l2_head = l1.next;
        //将新旧节点分离开来
        while (l1 != null) { 
            l2 = l1.next;
            l1.next = l2.next;
            if (l2.next != null) { 
                l2.next = l2.next.next;
            }
            l1 = l1.next;
        }
        return l2_head;
    }

/* // 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; } }; */
    public class Solution { 
      public Node copyRandomList(Node head) { 
    
        if (head == null) { 
          return null;
        }
    
        // Creating a new weaved list of original and copied nodes.
        Node ptr = head;
        while (ptr != null) { 
    
          // Cloned node
          Node newNode = new Node(ptr.val);
    
          // Inserting the cloned node just next to the original node.
          // If A->B->C is the original linked list,
          // Linked list after weaving cloned nodes would be A->A'->B->B'->C->C'
          newNode.next = ptr.next;
          ptr.next = newNode;
          ptr = newNode.next;
        }
    
        ptr = head;
    
        // Now link the random pointers of the new nodes created.
        // Iterate the newly created list and use the original nodes' random pointers,
        // to assign references to random pointers for cloned nodes.
        while (ptr != null) { 
          ptr.next.random = (ptr.random != null) ? ptr.random.next : null;
          ptr = ptr.next.next;
        }
    
        // Unweave the linked list to get back the original linked list and the cloned list.
        // i.e. A->A'->B->B'->C->C' would be broken to A->B->C and A'->B'->C'
        Node ptr_old_list = head; // A->B->C
        Node ptr_new_list = head.next; // A'->B'->C'
        Node head_old = head.next;
        while (ptr_old_list != null) { 
          ptr_old_list.next = ptr_old_list.next.next;
          ptr_new_list.next = (ptr_new_list.next != null) ? ptr_new_list.next.next : null;
          ptr_old_list = ptr_old_list.next;
          ptr_new_list = ptr_new_list.next;
        }
        return head_old;
      }
    }

###### 6. O(1)空间 (用原链表的 random域保存新生成的节点) ######

可以利用原链表的 random 域把新生成的节点保存起来。  
主要还是三个步骤。

1.  生成所有的节点，将它们保存到原链表的 random 域，同时利用新生成的节点的 next 域保存原链表的 random。
2.  更新新生成节点的 random 指针。
3.  恢复原链表的 random 指针，同时更新新生成节点的 next 指针。

**时间复杂度：O(N) 空间复杂度：O(1)**

public Node copyRandomList(Node head) { 
        if (head == null) { 
            return null;
        }
        Node l1 = head;
        Node l2 = null;
        //生成所有的节点，讲它们保存到原链表的 random 域，
        //同时利用新生成的节点的 next 域保存原链表的 random。
        while (l1 != null) { 
            l2 = new Node(l1.val);
            l2.next = l1.random;
            l1.random = l2;
            l1 = l1.next;
        }
        l1 = head;
        //更新新生成节点的 random 指针。
        while (l1 != null) { 
            l2 = l1.random;
            l2.random = l2.next != null ? l2.next.random : null;
            l1 = l1.next;
        }
    
        l1 = head;
        Node l2_head = l1.random;
        //恢复原链表的 random 指针，同时更新新生成节点的 next 指针。
        while (l1 != null) { 
            l2 = l1.random;
            l1.random = l2.next;
            l2.next = l1.next != null ? l1.next.random : null;
            l1 = l1.next;
        }
        return l2_head;
    }

#### 【总结】 ####

###### 1.思路1暴力O（N^2）-> 思路2.3.4 HashMap O(N)->思路5.6 复制链表O（1） ######

###### 2.链表操作的核心思想就是，在改变某一个节点的指针域的时候，一定要把该节点的指针指向的节点用另一个指针保存起来，以免造成丢失。 ######

###### 3.链表 画图 ######

转载链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-32/  
转载链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-32/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/5130f5b049814075ab20befd0bc6a31d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200723113113932.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200723113126515.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200723113046371.png]: https://img-blog.csdnimg.cn/20200723113046371.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200723134257800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200723134319425.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70