
复杂链表的复制
题目:
请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。(题目来自剑指Offer)
示例:
解法:
let copyRandomList = (head) => { if (!head) return null; let map = new Map(); let newHead = new Node(head.val), node = head, newNode = newHead; // 将node与newNode关联起来,方便后面复制随机节点 map.set(node, newNode); // 循环复制单链表 while (node.next) { newNode.next = new Node(node.next.val); node = node.next; newNode = newNode.next; map.set(node, newNode); } // 重置新节点和链头 newNode = newHead; node = head; // 循环复制随机节点 while (newNode) { newNode.random = map.get(node.random); newNode = newNode.next; node = node.next; } return newHead; };
评论(0)