【算法】复制含有随机指针节点的链表

MapleYe

发布于 2020-03-28 21:00:27

8750

文章被收录于专栏：MapleYeMapleYe

题目

一种特殊的链表节点类描述如下:

  public static class Node {
    public int value;
        public Node next;
        public Node rand;

        public Node(int data) {
            this.value = data;
        }
  }

next指针和正常单链表中next指针的意义一样，都指向下一个节点， rand指针是Node类中新增的指针，这个指针可能指向链表中的任意一个节点，也可能指向null。给定一个由 Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表中所有结构的复制，并返回复制的新链表的头节点。

进阶要求

不使用额外的数据结构，只用有限几个变量，且在时间复杂度为 O(N) 内完成原问题要实现的函数

基础解法

思路

1、使用hashMap，以Node为键，给每个Node创建一个副本 2、最后根据原来链表的next指针和rand指针，重连hashMap中的节点

算法实现

  public static Node copyListWithRand1(Node head) {
    HashMap<Node, Node> map = new HashMap<Node, Node>();
    Node cur = head;
    // 将节点备份到哈希表中
    while(cur != null) {
      map.put(cur, new Node(cur.value));
      cur = cur.next;
    }
    cur = head;
    // 根据原来链表的next指针和rand指针，重连hashMap中的节点
    while(cur != null) {
      map.get(cur).next = map.get(cur.next);
      map.get(cur).rand = map.get(cur.rand);
      cur = cur.next;
    }
    return map.get(head);
  }

进阶解法

思路

1、拷贝节点，例如对于 1->2->3->4 我们插入每个节点的后面插入其copy节点，使之为 1->1'->2->2'->3->3'->4->4' 2、那么我们通过找到源节点，即可找到其copy节点的位置（源节点.next），相当于哈希表的作用 3、最后根据原链表的rand关系，链接copy节点的rand指针 4、最后将链表拆分为原链表和copy链表

算法实现

  public static Node copyListWithRand2(Node node) {
    if(node == null) {
      return node;
    }
    Node cur = node;
    while(cur != null) {
      Node next = cur.next;
      // 拷贝节点，并插入其后
      Node copy = new Node(cur.value);
      copy.next = cur.next;
      cur.next = copy;
      cur = next;
    }
    // 连接rand指针
    cur = node;
    Node copyNode = cur.next;
    while(cur != null) {
      if(cur.rand != null) {
        // 由于cur.rand.next就是cur.rand的拷贝节点
        // 因此copyNode.rand指针，指向cur.rand.next
        copyNode.rand = cur.rand.next;
      }
      cur = cur.next.next;
      if(cur != null) {
        copyNode = cur.next;
      }
    }
    // 拆分链接
    cur = node;
    copyNode = cur.next;
    Node copyHead = cur.next;
    while(cur != null) {
      // 保存next指针
      Node tmp = copyNode.next;
      cur.next = copyNode.next;
      copyNode.next = cur.next;

      cur = tmp;
      if(cur != null) {
        copyNode = cur.next;
      }
    }
    return copyHead;
  }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

node.js