力扣 138 复制带随机指针的链表

题意：给定一个有随机指针的链表，把链表复制

思路：见代码注释

思想：链表的复制

复杂度：时间O（n)，空间O(n)

class Solution {
    public Node copyRandomList(Node head) {
        Node runner = head;
        // 复制每一个节点，并把复制的节点加到原链表的每一个节点之后
        while(runner != null) {
            Node temp = new Node(runner.val);
            temp.next = runner.next;
            runner.next = temp;
            runner = temp.next;
        }
        
        runner = head;
        // 把每一个复制的几点指向对应的random节点
        while(runner != null) {
            if(runner.random != null) {
                runner.next.random = runner.random.next;
            }
            runner = runner.next.next;
        }
        
        Node res = new Node(0);
        Node runner1 = res;
        runner = head;
        // 把每一个复制的节点拿出来组成结果链表
        while(runner != null) {
            runner1.next=runner.next;
            runner.next = runner.next.next;
            runner = runner.next;
            runner1 = runner1.next;
        }
        
        return res.next;
    }
}