题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

解题思路

1.在每个节点后面插入复制的结点
2.把复制的结点的random指针指向原来结点的random指针指向的结点的下一个结点
3.拆分为两个链表

  1. # -*- coding:utf-8 -*-
  2. # class RandomListNode:
  3. #     def __init__(self, x):
  4. #         self.label = x
  5. #         self.next = None
  6. #         self.random = None
  7. class Solution:
  8.     # 返回 RandomListNode
  9.     def Clone(self, pHead):
  10.         # write code here
  11.         if not pHead:
  12.             return None
  13.         #1.在每个结点后面插入要复制的结点
  14.         cur = pHead
  15.         while cur:
  16.             temp = RandomListNode(cur.label)
  17.             temp.next = cur.next
  18.             cur.next = temp
  19.             cur = temp.next
  20.         #2.把复制的结点的random指针指向原节点random指针所指向结点的下一个结点
  21.         cur = pHead
  22.         while cur:
  23.             temp = cur.next
  24.             if cur.random:
  25.                 temp.random = cur.random.next
  26.             cur = temp.next
  27.         #3.拆分为两个链表
  28.         cur = pHead
  29.         pCloneHead = cur.next
  30.         while cur:
  31.             temp = cur.next
  32.             curNext = temp.next
  33.             cur.next = curNext
  34.             if curNext:
  35.                 temp.next = curNext.next
  36.             else:
  37.                 temp.next = None
  38.             cur = curNext
  39.         return pCloneHead