题解 | #复杂链表的复制#

/**
 * class RandomListNode(var label: Int) {
 *     var next: RandomListNode? = null
 *     var random: RandomListNode? = null
 * }
 */
object Solution {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    * 
        * @param pHead ListNode类 
        * @return ListNode类
    */
    fun Clone(pHead: RandomListNode?): RandomListNode?  {
        if(pHead == null) return pHead
        var next = pHead
        var temp = pHead
        //在当前节点创建新的一个节点使之成为当前节点的next
        while(next != null) {
            temp = next.next
            var node = RandomListNode(next.label)
            next!!.next = node
            node.next = temp
            next = temp
        }
        next = pHead
        //要复制随机节点只需要把原节点的随机节点的内存地址所指向的节点的下一个节点就是所要找的新的随机节点的地址（因为新复制的节点是插入到原节点的下一个）
        while(next != null) {
            temp = next.next
            temp!!.random = next.random?.next
            next = next.next?.next
        }
        var newHead = RandomListNode(0)
        temp = newHead
        next = pHead
        //把原节点的next指向原来的next，复制节点指向复制的next
        while(next != null) {
            temp!!.next = next.next
            temp = temp?.next
            next.next = next.next?.next
            next = next?.next
        }
        return newHead.next
    }
}