剑指 Offer 35. 复杂链表的复制

爱被打了一巴掌 2024-03-23 15:20 26阅读 0赞

#### 目录 ####

*   *  题目思路
     *  代码实现

题目来源  
[剑指 Offer 35. 复杂链表的复制][Offer 35.]

### 题目思路 ###

利用哈希表的查询特点，考虑构建 原链表节点 和 新链表对应节点 的键值对映射关系，再遍历构建新链表各节点的 next 和 random 引用指向即可。

**算法流程：**

*  若头节点 head 为空节点，直接返回 null ；
 *  初始化： 哈希表map， 节点 cur 指向头节点；
 *  复制链表：
    
     *  建立新节点，并向 map 添加键值对 (原 cur 节点, 新 cur 节点） ；
     *  cur 遍历至原链表下一节点；
 *  构建新链表的引用指向：
    
     *  构建新节点的 next 和 random 引用指向；
     *  cur 遍历至原链表下一节点；
 *  返回值： 新链表的头节点 map\[head\] ；

### 代码实现 ###

/*
    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    */
    class Solution {
        
        public Node copyRandomList(Node head) {
        
            if(head == null){
        
                return null;
            }
            //初始化hash表
            HashMap<Node,Node> map = new HashMap();
            Node cur = head;
            //复制一个新的节点
            while(cur != null){
        
                map.put(cur,new Node(cur.val));
                cur = cur.next;
            }
            cur = head;
            //构建新链表的 next 和 random 指向
            while(cur != null){
        
                map.get(cur).next = map.get(cur.next);
                map.get(cur).random = map.get(cur.random);
                cur = cur.next;
            }
            //返回头节点
            return map.get(head);
        }
    }

![在这里插入图片描述][9d64c197fc354d498354914e575cb86b.png]

[Offer 35.]: https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/
[9d64c197fc354d498354914e575cb86b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/a129cc9ca8f24fde925e9b5665275be8.png