剑指offer35-复杂链表的复制

原题(来源Leetcode)

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

示例 1:

剑指offer35-复杂链表的复制

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

示例 2:

剑指offer35-复杂链表的复制

输入: head = [[1,1],[2,1]] 输出: [[1,1],[2,1]]

示例 3:

剑指offer35-复杂链表的复制

输入: head = [[3,null],[3,0],[3,null]] 输出: [[3,null],[3,0],[3,null]]

示例 4:

输入: head = [] 输出: [] 解释: 给定的链表为空(空指针),因此返回 null。

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000 。

注意: 本题与主站 138 题相同:https://leetcode-cn.com/problems/copy-list-with-random-pointer/

解法

思想

我第一个想到的居然是Spring IOC解决循环依赖的思想。。先扫描一遍把节点都缓存下来,并用HashMap记录新旧节点的对应关系,然后再扫描一遍设置random节点。

代码

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map = new HashMap<>();
        Node sentinel = new Node(0);
        Node curOld = head;
        Node curNew = sentinel;
        while(curOld!=null ){
            Node copy = new Node(curOld.val);
            curNew.next = copy;
            curNew = copy;
            map.put(curOld,copy);
            curOld = curOld.next;
        }
        for(Map.Entry<Node,Node> entry:map.entrySet()){
            Node old = entry.getKey();
            if(old.random != null)
                map.get(old).random = map.get(old.random);
        }
        return sentinel.next;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer35-%e5%a4%8d%e6%9d%82%e9%93%be%e8%a1%a8%e7%9a%84%e5%a4%8d%e5%88%b6/

发表回复

登录后才能评论