复杂链表的复制（Hard）

时间：2021-06-16 04:13:57

问题来源：选自LeetCode 138：复制带随机指针的链表

问题描述：

复杂链表的复制（Hard）

题目给定信息：

　　该链表中每一个节点的成员变量都有两个，一个是next指针指向该节点的下一个节点，一个是random指针指向不确定，可以指向该链表中任意一个节点，也可以指向它自己，还可以指向为空，我们要克隆这个链表，并且保证每一个链表节点的两个指针都和原链表是一样的。

问题分析：

复杂链表的复制（Hard）

　　我们可以间接的利用节点地址和节点序号之间的映射关系，在Map集合中存贮两个链表（原链表和新建待克隆链表）的映射关系。通过一个while循环，创建出和每个链表节点值相同的节点，并且把这些节点都按照映射关系存进Map集合中，在这个循环中还能把新创建的节点的next指针赋上相应的值。然后再经过一个while循环，每遍历到原链表的一个节点，我们就在Map集合中找到该节点映射对应的新创建节点是哪一个，这样就能给新创建的节点的random指针进行赋值操作，便利循环结束，新创建的每一个节点的random指针也全部赋值结束。返回新创建的链表头指针就可以了。

函数实现：

方法一：

  public Node copyRandomList(Node head) {

         if (head == null) {

             return null;

         }

         Node newHead = new Node(head.val, null, null);

         Node temp = head.next;

         Node temp_New = newHead;

         Map<Node, Node> map = new HashMap<>();

         map.put(head, newHead);

         while (temp != null) {

             Node newList = new Node(temp.val, null, null);

             map.put(temp, newList);

             temp_New.next = newList;

             temp_New = newList;

             temp = temp.next;

         }

         temp = head;

         temp_New = newHead;

         while (temp != null) {

             temp_New.random = map.get(temp.random);

             temp = temp.next;

             temp_New = temp_New.next;

         }

         return newHead;

     }

方法二：

 public Node copyRandomList(Node head) {

         Map<Node, Integer> map = new HashMap<Node, Integer>();

         Vector<Node> vector = new Vector<Node>();

         Node node = head;

         int i = 0;

         while (node != null) {

             vector.add(new Node(node.val, null, null));

             map.put(node, i);

             node = node.next;

             i++;

         }

         node=head;

         i=0;

         while(node!=null){

             vector.get(i).next=vector.get(i+1);

             if(node.random!=null){

                 int id=map.get(node);

                 vector.get(i).random=vector.get(id);

             }

             node=node.next;

             i++;

         }

         return vector.get(0);

     }

运行结果：

复杂链表的复制（Hard）

相关文章