复杂链表的复刻（三十六）

本文主要是介绍复杂链表的复刻（三十六），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目
请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

注意：

函数结束后原链表要与输入时保持一致。

算法
思想：将当前节点复制一份并且插入到当前节点的后面，然后再链接虚拟节点，最后进行拆分。不能直接返回原链表，系统会判别，最后还要将原链表恢复。
时间复杂度：O(n)
在这里插入图片描述

class Solution {public ListNode copyRandomList(ListNode head) {//第一次遍历将每个节点复制一份插入到当前节点的后面for(ListNode p = head;p != null;){ListNode newP = new ListNode(p.val);ListNode next = p.next;p.next = newP;newP.next = next;p = next;}//为复制的节点添加随机节点for(ListNode p = head;p != null;p = p.next.next){if(p.random != null){p.next.random = p.random.next;}}ListNode dummy = new ListNode(-1);ListNode cur = dummy;for(ListNode p = head;p != null;p = p.next){cur.next = p.next;cur = cur.next;//这一步操作是为了还原链表p.next = p.next.next;}return dummy.next;}
}

其他做法：
用hashmap将每个节点先进行copy，然后用原节点做key，复制节点做value存进hashmap
然后遍历链表，把复制节点取出连好即可，因为hashmap的增删改查是O（n）。所以时间复杂度很低。

class Solution {public ListNode copyRandomList(ListNode head) {if(head==null)return null;Map<ListNode,ListNode> copy = new HashMap<>();ListNode node = head;while(node!=null){ListNode CloneNode = new ListNode(node.val);copy.put(node,CloneNode);node = node.next;}node = head;ListNode CloneHead = copy.get(node);ListNode CloneNode = CloneHead;while(node!=null){CloneNode.next = copy.get(node.next);if(node.random!=null){CloneNode.random = copy.get(node.random);}CloneNode = CloneNode.next;node = node.next;}return CloneHead;}
}