复杂链表的复制

题目

牛客网

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

解题思路

  1. 复制每个节点,如:复制节点 A 得到 A1 ,将 A1 插入节点 A 后面
  2. 遍历链表,并将 A1->random = A->random->next;
  3. 将链表拆分成原链表和复制后的链表
  1. public RandomListNode Clone(RandomListNode pHead) {
  2. if (pHead == null) {
  3. return null;
  4. }
  5. RandomListNode cursor = pHead;
  6. while (cursor != null) {
  7. RandomListNode copyNode = new RandomListNode(cursor.label);
  8. RandomListNode nextNode = cursor.next;
  9. cursor.next = copyNode;
  10. copyNode.next = nextNode;
  11. cursor = nextNode;
  12. }
  13. cursor = pHead;
  14. while (cursor != null) {
  15. RandomListNode copyNode = cursor.next;
  16. if (cursor.random == null) {
  17. cursor = copyNode.next;
  18. continue;
  19. }
  20. copyNode.random = cursor.random.next;
  21. cursor = copyNode.next;
  22. }
  23. RandomListNode copyHead = pHead.next;
  24. cursor = pHead;
  25. while (cursor.next != null) {
  26. RandomListNode copyNode = cursor.next;
  27. cursor.next = copyNode.next;
  28. cursor = copyNode;
  29. }
  30. return copyHead;
  31. }