138. 复制带随机指针的链表

题意：

解题思路：

思路：O(n)
第一步，将新生成的结点放在原结点的后边，即 1 -> 1' -> 2 -> 2' -> NULL。新结点的随机指针指向原结点。
第二步，扫描合成的链表，更新新结点的随机指针为原来指向结点的 next。//$p->next->random = $p->random->next;
第三步，将两个链表分离，恢复原链表，返回新链表的头结点。

PHP代码实现：

/**
 * Definition for a Node.
 * class Node {
 *     public $val = null;
 *     public $next = null;
 *     public $random = null;
 *     function __construct($val = 0) {
 *         $this->val = $val;
 *         $this->next = null;
 *         $this->random = null;
 *     }
 * }
 */
class Solution {
    /**
     * @param Node $head
     * @return Node
     */
    function copyRandomList($head) {
        //复制一个小弟
        for ($p = $head; $p; $p = $p->next->next) {
            $q = new Node($p->val);
            $q->next = $p->next;
            $p->next = $q;
        }
        //复制random指针
        for ($p = $head; $p; $p = $p->next->next) {
            if ($p->random) {
                $p->next->random = $p->random->next;
            }
        }
        //拆分两个链表
        $dummy = new Node(-1);
        $cur = $dummy;
        for ($p = $head; $p; $p = $p->next) {
            $q = $p->next;
            $cur = $cur->next = $q;
            $p->next = $q->next;
        }
        return $dummy->next;
    }
}

GO代码实现：

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */
func copyRandomList(head *Node) *Node {
    if head == nil {
        return head
    }
    // 复制节点，紧挨到到后面
    // 1->2->3  ==>  1->1'->2->2'->3->3'
    cur := head
    for cur != nil {
        clone := &Node{Val: cur.Val, Next: cur.Next}
        temp := cur.Next
        cur.Next = clone
        cur = temp
    }
    // 处理random指针
    cur = head
    for cur != nil {
        if cur.Random != nil {
            cur.Next.Random = cur.Random.Next
        }
        cur = cur.Next.Next
    }
    // 分离两个链表
    cur = head
    cloneHead := cur.Next
    for cur != nil && cur.Next != nil {
        temp := cur.Next
        cur.Next = cur.Next.Next
        cur = temp
    }
    // 原始链表头：head 1->2->3
    // 克隆的链表头：cloneHead 1'->2'->3'
    return cloneHead
}