technology-note/算法/leetcode/常规题/Q1744.复制带随机指针的链表.md

id	date	title	tags	categories
202203031	2022/03/03 20:38:05	leetcode.Q1744.复制带随机指针的链表	java leetcode 链表	算法 leetcode刷题

解析思路

leetcode 中等，题目描述点击这里。

比较简单，链表结构可以通过遍历复制，关键是random节点如何处理，这里提供一个处理思路：

通过两次遍历来实现：

• 第一次遍历建立新的链表，不处理random，遍历的同时将旧链表节点和新链表节点做一个一一对应
• 第二次遍历处理random节点，根据map找到新链表的位置

代码

public class Q138 {
    private static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        //老节点和新节点的对应关系
        Map<Node, Node> oldNewMap = new HashMap<>();
        //建立虚拟头节点便于处理
        Node res = new Node(0), tempNew = res, tempOld = head;
        while (tempOld != null) {
            tempNew.next = new Node(tempOld.val);
            tempNew = tempNew.next;
            //旧节点和新节点一一对应
            oldNewMap.put(tempOld, tempNew);
            tempOld = tempOld.next;
        }
        //再次便利将random关系处理好
        while (head != null) {
            if (head.random != null) {
                oldNewMap.get(head).random = oldNewMap.get(head.random);
            }
            head = head.next;
        }
        return res.next;
    }
}