题目描述
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点)。
下面是我第一想到的思路:因为next指针是固定的,在复制的时候这点比较好处理,由于特殊指针是任意的,可能是在节点之前,也可能在节点之后,所以必须解决这个棘手问题。不管至少,可以从链表的第一个节点开始遍历,直到该特殊指针指向的节点,并设置该节点的特殊指针。还有一种思路(也是书上的思路):第一步,复制原来链表的节点,并设置next指针,这一步不同于简单的复制节点,而是把每个复制的节点都链在原节点的后面,相当于复制节点之间隔了一个原节点;第二步,设置复制节点的特殊指针,由于在第一步左了特殊处理,所以当一个节点R的特殊指针指向节点N的时候,复制节点R’的特殊指针则是N’,这样就可以在O(1)时间定位到R的特殊指针指向的节点;第三步,从链表中抽取出复制节点,由于复制节点是间隔相连的,所以这一步比较好处理。综合以上三个步骤,就完成了复杂链表的复制。
下面是基于第二种思路的Java代码(已被牛客AC):
package com.rhwayfun.offer;
public class CopyComplicateLinkedList {
static class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
public RandomListNode Clone(RandomListNode pHead) {
CloneNodes(pHead);
ConnectSiblingNodes(pHead);
return ConnectFinalListNodes(pHead);
}
// 第一步:复制链表节点
private void CloneNodes(RandomListNode pHead) {
RandomListNode node = pHead;
while (node != null) {
RandomListNode cloneNode = new RandomListNode(node.label);
cloneNode.next = node.next;
cloneNode.random = null;
node.next = cloneNode;
node = cloneNode.next;
}
}
// 第二步:设置每个节点的随机指针
private void ConnectSiblingNodes(RandomListNode pHead) {
RandomListNode node = pHead;
while (node != null) {
RandomListNode clone = node.next;
if (node.random != null) {
clone.random = node.random.next;
}
node = clone.next;
}
}
// 第三步:组合复制的节点
private RandomListNode ConnectFinalListNodes(RandomListNode pHead) {
RandomListNode node = pHead;
RandomListNode cloneHead = null;
RandomListNode cloneNode = null;
// 设置第一个节点
if (node != null) {
cloneHead = node.next;
cloneNode = node.next;
node.next = cloneNode.next;
node = node.next;
}
while (node != null) {
cloneNode.next = node.next;
cloneNode = cloneNode.next;
node.next = cloneNode.next;
node = node.next;
}
return cloneHead;
}
public static void main(String[] args) {
RandomListNode pHead = new RandomListNode(1);
RandomListNode node1 = new RandomListNode(2);
RandomListNode node2 = new RandomListNode(3);
RandomListNode node3 = new RandomListNode(4);
RandomListNode node4 = new RandomListNode(5);
RandomListNode node5 = new RandomListNode(6);
RandomListNode node6 = new RandomListNode(7);
RandomListNode node7 = new RandomListNode(8);
pHead.next = node1;
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node6.next = node7;
pHead.random = node4;
node2.random = node6;
@SuppressWarnings("unused")
RandomListNode node = new CopyComplicateLinkedList().Clone(pHead);
System.out.println(node);
}
}
时间: 2024-09-23 17:27:00