首页 > 代码库 > 【LeetCode】Copy List with Random Pointer 解题报告

【LeetCode】Copy List with Random Pointer 解题报告

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */

【题意】

深拷贝一个链表,链表除了含有next指针外,还包含一个random指针,该指针指向字符串中的某个节点或者为空。

【思路一】(来自网络)

假设原始链表如下,细线表示next指针,粗线表示random指针,没有画出的指针均指向NULL:

原链表

构建新节点时,指针做如下变化,即把新节点插入到相应的旧节点后面:

新结点插入到原结点之后

【Java代码】

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        //第一遍扫描:对每个结点进行复制,把复制出来的新结点插在原结点之后
        RandomListNode node = head;
        while (node != null) {
            RandomListNode newnode = new RandomListNode(node.label);
            newnode.next = node.next;
            node.next = newnode;
            node = newnode.next;
        }
        
        //第二遍扫描:根据原结点的random,给新结点的random赋值
        node = head;
        while (node != null) {
            if (node.random != null) node.next.random = node.random.next;
            node = node.next.next;
        }
        
        RandomListNode newhead = head.next;
        
        //第三遍扫描:把新结点从原链表中拆分出来
        node = head;
        while (node != null) {
            RandomListNode newnode = node.next;
            node.next = newnode.next;
            if (newnode.next != null) newnode.next = newnode.next.next;
            node = node.next;
        }
        
        return newhead;
    }
}


【参考】

http://www.cnblogs.com/TenosDoIt/p/3387000.html

http://blog.csdn.net/linhuanmars/article/details/22463599

【LeetCode】Copy List with Random Pointer 解题报告