获取节点索引 | #复杂链表的复制#

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if pHead:
            my_pHead = RandomListNode(pHead.label)
            my_cur_node = my_pHead
            cur_node = pHead
            node_len = 1
            while cur_node.next:
                cur_node = cur_node.next
                # print(cur_node.label)
                my_cur_node.next = RandomListNode(cur_node.label)
                my_cur_node = my_cur_node.next
                node_len += 1

            my_cur_node = my_pHead
            cur_node = pHead
            while cur_node:
                # print(cur_node.label)
                rnd_node = cur_node.random
                if not rnd_node:
                    my_cur_node.random = None
                    cur_node = cur_node.next
                    my_cur_node = my_cur_node.next
                    continue
                rnd_cnt = 0
                my_rnd_node = my_pHead
                while rnd_node and rnd_node.next:  # 取得random指向节点的倒序索引
                    rnd_node = rnd_node.next
                    rnd_cnt += 1
                # print(rnd_cnt)
                rnd_idx = node_len-1-rnd_cnt  # 取得random节点的正序索引
                # print(rnd_idx)
                while rnd_idx > 0:  # 根据正序索引建立复制链表的random链接
                    my_rnd_node = my_rnd_node.next
                    rnd_idx -= 1
                # print(my_cur_node.label, my_rnd_node.label)
                my_cur_node.random = my_rnd_node
                cur_node = cur_node.next
                my_cur_node = my_cur_node.next
            return my_pHead
        else:
            return None

如上，该题的关键在于获取random节点的索引，然后根据索引建立复制品的random链接