# 复杂链表的复制

+关注继续查看

public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}

• 暴力的解法：首先只复制链表，不管random指针。然后再遍历原链表，复制random指针。复制random指针的方法是根据原链表从头开始，而指向复制链表的指针也同时开始，判断random指针是指向哪一个结点，然后根据位置对应，把复制链表的指针的位置赋值给random。好吧，其实画个图很简单。

import java.util.*;

public class Main {

class RandomListNode{
public int label;
public RandomListNode next = null;
public RandomListNode random = null;

public RandomListNode(int label){
this.label = label;
}
}

public RandomListNode Clone(RandomListNode pHead){
if(pHead == null)
return null;
RandomListNode temp = pHead;
RandomListNode head = new RandomListNode(temp.label);
RandomListNode p = head;
if(temp.next != null)
temp = temp.next;
//首先把只复制基本的链表

while (temp != null){
RandomListNode node = new RandomListNode(temp.label);
p.next = node;
node.next = null;
p = p.next;
temp = temp.next;
}
//然后复制random指针
p = head;
temp = pHead;
while (p != null){
if(temp.random == null){
p.random = null;
p = p.next;
temp = temp.next;
continue;
}

RandomListNode t = pHead;
RandomListNode q = head;
while(t != null){ //t和q只需要判断一个就行
if(temp.random == t)
break;
t = t.next;
q = q.next;
}

p.random = q;
p = p.next;
temp = temp.next;
}
return head;
}

public static void main(String[] args) {
RandomListNode node1 = new Main().new RandomListNode(1);
RandomListNode node2 = new Main().new RandomListNode(2);
RandomListNode node3 = new Main().new RandomListNode(3);
RandomListNode node4 = new Main().new RandomListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = null;
node1.random = null;
node3.random = node1;
RandomListNode head = new Main().Clone(node1);
System.out.println(head);
System.out.println(head.random);
head = head.next;
System.out.println(head.random);
head = head.next;
System.out.println(head.random);
}
}

• 本题一种巧妙的解法是，将每个复制后的结点都跟在原结点后面，步骤如下：
1.复制每个结点，如复制结点A得到A1，并将A1插到结点A后面。
2.重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next
3.拆分链表，将原链表拆分成原链表和复制后的链表
import java.util.*;

public class Main {

class RandomListNode{
public int label;
public RandomListNode next = null;
public RandomListNode random = null;

public RandomListNode(int label){
this.label = label;
}
}

public RandomListNode Clone(RandomListNode pHead){
if(pHead == null)
return null;
RandomListNode currentNode = pHead;
//1.复制每个结点，如复制结点A得到A1，将A1插到A后面
while (currentNode != null){
RandomListNode copyNode = new RandomListNode(currentNode.label);
RandomListNode p = currentNode.next;
copyNode.next = p;
currentNode.next = copyNode;
currentNode = p;
}

//2.重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next
currentNode = pHead;
while (currentNode != null){
currentNode.next.random = (currentNode.random == null) ? null : currentNode.random.next;
currentNode = currentNode.next.next;
}

//3.拆分链表，将原链表拆分成原链表和复制后的链表
currentNode = pHead;
RandomListNode copyHead = currentNode.next;
while (currentNode != null){
RandomListNode p = currentNode.next;
currentNode.next = p.next;
if(p.next != null)
p.next = p.next.next;
currentNode = currentNode.next;
}
return copyHead;
}

public static void main(String[] args) {
RandomListNode node1 = new Main().new RandomListNode(1);
RandomListNode node2 = new Main().new RandomListNode(2);
RandomListNode node3 = new Main().new RandomListNode(3);
RandomListNode node4 = new Main().new RandomListNode(4);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = null;
node1.random = null;
node3.random = node1;
RandomListNode head = new Main().Clone(node1);
System.out.println(head);
System.out.println(head.random);
head = head.next;
System.out.println(head.random);
head = head.next;
System.out.println(head.random);
}
}

【LeetCode】第16天 - 234. 回文链表
【LeetCode】第16天 - 234. 回文链表
0 0
LeetCode笔记 | 链表（ing）
LeetCode笔记 | 链表（ing）
0 0

0 0
LeetCode排序链表C++解法（详解）

0 0
leetcode 链表的中间结点

0 0
leetcode 删除链表的倒数第 N 个结点

0 0
LeetCode 23合并K个升序链表&24两两交换链表中的节点

0 0
LeetCode 25K 个一组翻转链表&26删除排序数组中的重复项

0 0
LeetCode 86分割链表&87扰乱字符串

0 0
+关注
woooow