剑指 Offer 35. 复杂链表的复制

剑指 Offer 35. 复杂链表的复制

请实现 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。

提示:

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

首先说明解题思路的时候,先简单说一下这个题主要是让返回的值是你自行复制的链表,也就是说可以采用暴力解法、哈希表或者开辟一个空间来创建一个链表让它进行返回,当然直接return head肯定不行。

一、暴力解法

这个暴力解法在LeetCode里面提交题解的时候,提示超出了时间限制,然后看了K神的代码以后,发现还可以再精简完善一些。

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        ArrayList<Node> list = new ArrayList<>();
        while(head!=null){
            list.add(head);
            head = head.next;
        }

       //创建结果集合并初始化
        ArrayList<Node> res = new ArrayList<>();
        for(int i = 0;i<list.size();++i){
            res.add(new Node(list.get(i).val));
        }
       //设置结果结合的 random和next
        for (int i = 0; i < list.size(); ++i) {
            res.get(i).random = list.get(i).random == null?null:res.get(list.indexOf(list.get(i).random));
            if(i!=list.size()-1) res.get(i).next = res.get(i+1);
        }

        return res.get(0);
    }
}

二、哈希表

这里主要的难点在看懂构建新链表的引用指向:

  • 构建新节点的next和random引用指向
  • cur遍历原链表到下一个节点
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node cur = head;
        Map<Node,Node> res = new HashMap<>();
        while(cur != null) {//遍历链表,并存储每个节点的新节点
            res.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;//重置cur
        while (cur != null) {
            res.get(cur).next = res.get(cur.next);//用cur.next指向res.get(cur).next
            res.get(cur).random = res.get(cur.random);//用cur.random指向res.get(cur).random
            cur = cur.next;
        }
        return res.get(head);//返回头结点是因为新链表的头结点也存着在res中
    }
}

三、递归

这个做题思路类似于dfs,创建一个节点之后,接着通过递归的方式创建他的next节点……(参考链接见下面)

class Solution {
    public Node copyRandomList(Node head) {
        //map存储已经创建的节点
        HashMap<Node, Node> map = new HashMap<>();
        return copyListHelper(head, map);
    }
public Node copyListHelper(Node head, HashMap<Node, Node> map) {
    if (head == null)
        return null;
    //如果节点创建了,直接从map中取
    if (map.containsKey(head))
        return map.get(head);
    //如果节点没有创建,就创建一个,然后使用递归的方式在创建他的
    //next节点和random节点
    Node res = new Node(head.val);
    map.put(head, res);
    res.next = copyListHelper(head.next, map);
    res.random = copyListHelper(head.random, map);
    return res;
    }
}

参考链接:

//leetcode-cn.com/leetbook/read/illustration-of-algorithm/9plk45/

//leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/shu-ju-jie-gou-he-suan-fa-di-gui-he-fei-wby85/