Skip to content

Latest commit

 

History

History
11 lines (8 loc) · 845 Bytes

File metadata and controls

11 lines (8 loc) · 845 Bytes

第一轮复制节点,使新节点链接在旧链表对应节点的后面:

        -------      -------      -------      -------
... -> | 旧nd i | ->| 新nd i | ->|旧nd i+1| -> |新nd i+1| -> ... 
        -------      -------      -------      -------

第二轮遍历复制random,新节点的random指向对应旧节点random指向节点对应的新节点,因为现在对应的新节点在旧节点之后,所以新节点的random指向对应纠结点random指向节点的下一节点

第三轮遍历将新链表的节点和旧链表的节点拆开,成为2个链表(这一步不能与第二轮遍历合并,因为后面的节点的random可能指向前面的节点,如果在设置random成员的同时拆链表,由于前面的节点已经拆开,所以新链表节点的random成员会指向旧链表的节点)