leetcode 138. Copy List with Random Pointer 链表复制 + HashMap

￡神魔★判官ぃ 2022-06-08 06:00 134阅读 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.

本题题意就是复制链表，**注意使用HashMap等结构保存相关信息**，这样更加方便。

代码如下：

import java.util.HashMap;
    import java.util.Map;
    
    /*class RandomListNode 
    {
          int label;
          RandomListNode next, random;
          RandomListNode(int x) { this.label = x; }
    };*/
    
    /*
     *  这个是用一个map映射关系来获取相关的信息，这样避免了直接复制的遍历开销
     * */
    public class Solution
    {
         public RandomListNode copyRandomList(RandomListNode head) 
         {
                if(head == null)
                    return head;
    
                Map<Integer, RandomListNode> map = new HashMap<>();
                Map<RandomListNode,Integer>  remap = new HashMap<>();
                Map<Integer, RandomListNode> newMap = new HashMap<>();
    
                RandomListNode newHead = new RandomListNode(-1);
                RandomListNode iter = head , newIter = newHead;
                int count = 0;
                while(iter!=null)
                {
                    newIter.next = new RandomListNode(iter.label);
    
                    map.put(count, iter.random);
                    remap.put(iter, count);
                    newMap.put(count,newIter.next);
    
                    newIter = newIter.next;
                    iter =iter.next;
                    count++;
                }
    
                newIter = newHead.next;
                count = 0;
                while(newIter!=null)
                {
                    RandomListNode ran = map.get(count);
                    if(ran==null)
                        newIter.random = null;
                    else
                    {
                        int key = remap.get(ran);
                        newIter.random = newMap.get(key);
                    }
                    newIter = newIter.next;
                    count++;
                }
                return newHead.next;
         }
    }