Java面试题-实现复杂链表的复制代码分享

我们来详细讲解一下“Java面试题-实现复杂链表的复制代码分享”的完整攻略。

确定复制思路

在复制带有随机指针的链表时，我们需要对每个节点都进行深拷贝，并且需要关联原链表中同样的随机指针，因此需要考虑以下几个步骤：

1. 添加新的节点
2. 复制原链表中的节点
3. 连接新旧链表
4. 复制随机指针

添加新的节点

首先，我们需要对原始链表中的每个节点进行拷贝，并且将拷贝后的节点插入在原始节点的后面。这里我们可以使用链表的插入方法，将新的节点插入到原始节点的后面，具体实现如下：

public static void cloneNodes(ComplexListNode head) {
    ComplexListNode node = head;
    while (node != null) {
        ComplexListNode cloned = new ComplexListNode(node.val);
        cloned.next = node.next;
        cloned.random = null;
        node.next = cloned;
        node = cloned.next;
    }
}

这里我们新创建了一个cloned节点，并且将其插入在node.next的位置上，之后我们更新node节点的指向，指向cloned节点的下一个节点，这样子便完成了新的节点的插入。

复制原链表中的节点

在第一步完成后，我们已经实现了对新链表节点的创建，接下来需要将原始链表中的节点复制到新链表中。对于每一个原始链表中存在的节点，我们可以通过链表的遍历，通过node.next获取到其对应的新链表中的节点，并且为新链表中对应的节点设置随机指针指向，具体实现如下：

public static void connectSiblingNodes(ComplexListNode head) {
    ComplexListNode node = head;
    while (node != null) {
        ComplexListNode cloned = node.next;
        if (node.random != null) {
            cloned.random = node.random.next;
        }
        node = cloned.next;
    }
}

这里，我们首先复制了head节点，并将其赋值给node，接下来我们进行遍历，每次取出原始节点的下一个节点，并且将其赋值给cloned节点。如果原始节点存在random指针，那么我们需要将其指向的节点在新链表中的节点赋值给cloned的random指针。

连接新旧链表

完成前两个步骤后，我们已经创建了与原始链表对应位置的新链表，并且为其连接了随机指针指向。接下来，我们需要将两个链表分开，并且返回只包含新链表的头结点。具体实现如下：

public static ComplexListNode reconnectNodes(ComplexListNode head) {
    ComplexListNode node = head;
    ComplexListNode clonedHead = null;
    ComplexListNode clonedNode = null;
    if (node != null) {
        clonedHead = clonedNode = node.next;
        node.next = clonedNode.next;
        node = node.next;
    }
    while (node != null) {
        clonedNode.next = node.next;
        clonedNode = clonedNode.next;
        node.next = clonedNode.next;
        node = node.next;
    }
    return clonedHead;
}

这里，我们首先取出原始链表中的第一个节点，并且根据第一步中新创建的节点，取出对应位置的新链表中的头结点，并将其赋值给clonedHead和clonedNode。接下来进行遍历，分别移动新旧链表中的指针，并将其连接起来。最后返回只包含新链表的头结点。

完整代码

将以上三步整合起来，我们得到完整的复制带随机指针链表的代码实现：

class ComplexListNode{
    int val;
    ComplexListNode next;
    ComplexListNode random;
    public ComplexListNode(int val) {
        this.val = val;
    }
}

public static ComplexListNode clone(ComplexListNode head) {
    cloneNodes(head);
    connectSiblingNodes(head);
    return reconnectNodes(head);
}

public static void cloneNodes(ComplexListNode head) {
    ComplexListNode node = head;
    while (node != null) {
        ComplexListNode cloned = new ComplexListNode(node.val);
        cloned.next = node.next;
        cloned.random = null;
        node.next = cloned;
        node = cloned.next;
    }
}

public static void connectSiblingNodes(ComplexListNode head) {
    ComplexListNode node = head;
    while (node != null) {
        ComplexListNode cloned = node.next;
        if (node.random != null) {
            cloned.random = node.random.next;
        }
        node = cloned.next;
    }
}

public static ComplexListNode reconnectNodes(ComplexListNode head) {
    ComplexListNode node = head;
    ComplexListNode clonedHead = null;
    ComplexListNode clonedNode = null;
    if (node != null) {
        clonedHead = clonedNode = node.next;
        node.next = clonedNode.next;
        node = node.next;
    }
    while (node != null) {
        clonedNode.next = node.next;
        clonedNode = clonedNode.next;
        node.next = clonedNode.next;
        node = node.next;
    }
    return clonedHead;
}

示例说明

假设我们有一个链表为：

1 -> 2 -> 3 -> null
|    |
V    V
2 -> 3

我们可以根据以上代码实现将其深拷贝，得到新的链表：

1 -> 2 -> 3 -> null
|    |
V    V
2 -> 3

其中新链表中的每个节点都与原始链表中对应，而且随机指针指向也正确。这里为了方便演示，我们只展示了一个示例。

阅读剩余 70%