复杂链表的复制-剑指Offer35-java

一、题目描述

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

示例 1：

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：

 

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、运行结果

三、解题思路

复制复杂链表的难点在于random指针的复制，这里使用一个哈希表来保存每一个院链表中的结点与对应的新链表中的结点之间的对应关系，在第一次遍历原链表进行复制的时候，先不处理每个新链表结点的random指针，只是保存新旧结点之间的对应关系。

简单对原链表复制完成之后（没有处理random指针），所有的结点都已经复制完成，在重头遍历一次链表，处理random指针，而random指针可以根据先前保存的对应关系进行设置，根据原链表中每个结点的random指针设置新链表中每个结点的random指针。

四、AC代码

/*
// 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) {Node p = head;           // 工作指针，遍历原链表Map<Node, Node> map = new HashMap<>(); //原结点和新结点之间的映射关系Node dummy = new Node(-1);if(head == null) return null;Node tmpNode = new Node(p.val);        //指向新构建的结点dummy.next = tmpNode;   Node rear = tmpNode;     //指向新构建链表的末尾结点map.put(head, tmpNode);while(p.next != null){   //先复制每个结点和next指针，先不管random指针Node pnext = p.next;tmpNode = new Node(pnext.val);rear.next = tmpNode; // 指针后移rear = tmpNode;p = pnext;map.put(pnext, tmpNode); // 保存映射关系}p = head;          // 再重头到尾扫描一遍链表tmpNode = dummy.next;while(p != null){  //构建random指针tmpNode.random = map.get(p.random);p = p.next;tmpNode = tmpNode.next;}return dummy.next;}
}