首页 > itarticle > LeetCode | Copy List with Random Pointer

LeetCode | Copy List with Random Pointer

admin 11月 11, 2020 0

原题描述

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.

解题思路

本题要复制的对象是带随机指针的单链表，随机指针指向单链表的某一个结点。
参考文章：http://blog.csdn.net/linhuanmars/article/details/22463599

实现代码

/** 
 * Copy List with Random Pointer 
 * @author wzystal 
 */  
public class Solution {  
    class RandomListNode {  
        int label;  
        RandomListNode next, random;  
  
        public RandomListNode(int x) {  
            this.label = x;  
        }  
    }  
  
    // 时间复杂度O(n),空间复杂度O(n)  
    public RandomListNode copyRandomList1(RandomListNode head) {  
        if (head == null)  
            return head;  
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();  
        RandomListNode newHead = new RandomListNode(head.label);  
        map.put(head, newHead);  
        RandomListNode pre = newHead;  
        RandomListNode node = head.next;  
        while (node != null) {  
            RandomListNode newNode = new RandomListNode(node.label);  
            map.put(node, newNode);  
            pre.next = newNode;  
            pre = pre.next;  
            node = node.next;  
        }  
        node = head;  
        RandomListNode copyNode = newHead;  
        while (node != null) {  
            copyNode.random = map.get(node.random);  
            copyNode = copyNode.next;  
            node = node.next;  
        }  
        return newHead;  
    }  
  
    // 时间复杂度O(n),空间复杂度O(1)  
    public RandomListNode copyRandomList2(RandomListNode head) {  
        if (head == null)  
            return head;  
        RandomListNode node = head;  
        while (node != null) {  
            RandomListNode newNode = new RandomListNode(node.label);  
            newNode.next = node.next;  
            node.next = newNode;  
            node = newNode.next;  
        }  
        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;  
    }  
}  