复杂链表的复制（剑指offer-25）

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

题目解析

题目解答

/*

public class RandomListNode {

    int label;

    RandomListNode next = null;

    RandomListNode random = null;

    RandomListNode(int label) {

        this.label = label;

    }

}

*/

import java.util.*;

public class Solution {

    public RandomListNode Clone(RandomListNode pHead){

        Map<RandomListNode,RandomListNode> map = new HashMap<>();

        RandomListNode removeNode = pHead;

        while(removeNode != null){

            RandomListNode node = new RandomListNode(removeNode.label);

            map.put(removeNode,node);

            removeNode = removeNode.next;

        }

        removeNode = pHead;

        while(removeNode != null){

            RandomListNode node = map.get(removeNode);

            node.next = map.get(removeNode.next);

            node.random = map.get(removeNode.random);

            removeNode = removeNode.next;

        }

        return map.getOrDefault(pHead,null);

    }

}

方法2

主要是通过创建新链表中的节点在原链表中，去优化了第一种方法的O(N)的空间复杂度，第二种方法分为三个过程

1->创建新节点以及实现新节点和元链表节点的连接

2->根据原链表的rangdom指向去生成新的节点的random的指向

3->链表的分割。

public RandomListNode Clone(RandomListNode pHead) {

        if (pHead == null) {

            return null;

        }

        // 第一个过程->创建新链表节点插入到原链表中

        RandomListNode removeNode = pHead;

        while (removeNode != null) {

            RandomListNode temp = removeNode.next;

            RandomListNode node = new RandomListNode(removeNode.label);

            removeNode.next = node; // 原节点指向新节点

            node.next = temp; // 新节点指向当前节点的next

            removeNode = temp;

        }

        // 第二个过程->创建rangdom节点指向

        removeNode = pHead;

        while (removeNode != null) {

            removeNode.next.random = removeNode.random == null ? null : removeNode.random.next;

            removeNode = removeNode.next.next; // 用两个next是把新链表节点隔过去

        }

        // 第三个过程->链表的分割

        removeNode = pHead;

        RandomListNode cloneHead = pHead.next;

        while (removeNode != null) {

            RandomListNode node = removeNode.next;

            removeNode.next = node.next; // 原链表中节点的结构之间关系的维护

            node.next = node.next == null ? null : node.next.next;// 维护新链表中节点关系的维护

            removeNode = removeNode.next;

        }

        return cloneHead;

    }

巴特西

复杂链表的复制（剑指offer-25）

题目描述

题目解析

题目解答

方法2

最新文章

热门文章