我们来详细讲解一下“Java面试题-实现复杂链表的复制代码分享”的完整攻略。
确定复制思路
在复制带有随机指针的链表时,我们需要对每个节点都进行深拷贝,并且需要关联原链表中同样的随机指针,因此需要考虑以下几个步骤:
- 添加新的节点
- 复制原链表中的节点
- 连接新旧链表
- 复制随机指针
添加新的节点
首先,我们需要对原始链表中的每个节点进行拷贝,并且将拷贝后的节点插入在原始节点的后面。这里我们可以使用链表的插入方法,将新的节点插入到原始节点的后面,具体实现如下:
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
其中新链表中的每个节点都与原始链表中对应,而且随机指针指向也正确。这里为了方便演示,我们只展示了一个示例。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java面试题-实现复杂链表的复制代码分享 - Python技术站