复杂链表的复制——牛客offer

题目描述：

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

数据结构：

public class RandomListNode {
int label; 数据域
RandomListNode next = null; 指向下一个结点
RandomListNode random = null; 指向任意一个节点

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

解题思路：

1、遍历链表，复制链表中的每个结点，并将复制的结点插入到该结点的后面。例如，原链表为A->B->C, 遍历完毕后，链表变为A->A'->B->B'->C->C'，其中A‘，B'，C'是结点A，B，C的复制结点。

看图中，蓝色箭头为next指针：

复制结点后：

2、为复制结点的random指针赋值

如果原结点的random指针指向的是结点B，那么将复制结点的random指针指向结点B的复制结点B'。

图中黑色箭头为random指针：

复制结点的random指针赋值后：

3、将链表的原始结点与复制结点分割至两个链表，使原始结点构成一个链表，复制结点构成一个链表。

代码实现：

1、复制结点

 //1.加入copy结点
public void copyNodes(RandomListNode pHead){ RandomListNode walkNode=pHead; while(walkNode!=null){ RandomListNode cloneNode=new RandomListNode(walkNode.label); cloneNode.next=walkNode.next; walkNode.next=cloneNode; walkNode=cloneNode.next; } }

更多相关文章

随机推荐