复杂链表的复制
题目
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的 head 。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
解题思路
- 复制每个节点,如:复制节点 A 得到 A1 ,将 A1 插入节点 A 后面
- 遍历链表,并将
A1->random = A->random->next
; - 将链表拆分成原链表和复制后的链表
public RandomListNode Clone(RandomListNode pHead) {
if (pHead == null) {
return null;
}
RandomListNode cursor = pHead;
while (cursor != null) {
RandomListNode copyNode = new RandomListNode(cursor.label);
RandomListNode nextNode = cursor.next;
cursor.next = copyNode;
copyNode.next = nextNode;
cursor = nextNode;
}
cursor = pHead;
while (cursor != null) {
RandomListNode copyNode = cursor.next;
if (cursor.random == null) {
cursor = copyNode.next;
continue;
}
copyNode.random = cursor.random.next;
cursor = copyNode.next;
}
RandomListNode copyHead = pHead.next;
cursor = pHead;
while (cursor.next != null) {
RandomListNode copyNode = cursor.next;
cursor.next = copyNode.next;
cursor = copyNode;
}
return copyHead;
}
当前内容版权归 Hayden Yang 或其关联方所有,如需对内容或内容相关联开源项目进行关注与资助,请访问 Hayden Yang .