1. 题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
2. 题目分析
- 链表中是有2个指针的，一个指向下一个节点，一个是指向随机的节点
- 想复制链表的话，第一步要复制链表
// 复制链表 RandomListNode current = pHead; while(current != null) { RandomListNode clone = new RandomListNode(current.label); clone.next = current.next; current.next = clone; current = clone.next; }
- 复制链表中的随机随机指针
// 复制随机random指针 current = pHead; while (current != null) { RandomListNode clone1 = current.next; if (current.random != null) { clone1.random = current.random.next; } current = clone1.next; }
- 拆分链表
// 拆分链表 current = pHead; RandomListNode listNode = pHead.next; RandomListNode list = listNode; while (current != null) { current.next = current.next.next; if(list.next != null) { list.next = list.next.next; } current = current.next; list = list.next; }
3. 题目代码
public class Solution { public static RandomListNode Clone(RandomListNode pHead) { if (pHead == null) { return null; } // 复制链表 RandomListNode current = pHead; while (current != null) { RandomListNode clone = new RandomListNode(current.label); clone.next = current.next; current.next = clone; current = clone.next; } // 复制随机random指针 current = pHead; while (current != null) { RandomListNode clone1 = current.next; if (current.random != null) { clone1.random = current.random.next; } current = clone1.next; } // 拆分链表 current = pHead; RandomListNode listNode = pHead.next; RandomListNode list = listNode; while (current != null) { current.next = current.next.next; if(list.next != null) { list.next = list.next.next; } current = current.next; list = list.next; } return listNode; } }
