剑指offer—复杂链表的复制 解答

剑指offer—复杂链表的复制

问题描述

给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。

要求返回这个链表的深拷贝。 


示例:


输入:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}
输出:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

解释:
节点 1 的值是 1,它的下一个指针和随机指针都指向节点 2 。
节点 2 的值是 2,它的下一个指针指向 null,随机指针指向它自己。

思路

  • 时间O(N),空间O(N):使用hash存储节点,进行复制添加
  • 时间O(N),空间O(1):把复制节点往旧链表中添加,最后拆分新链表并且维护旧链表

我们主要看方法二:

我们迭代复制每一个链表中的节点,并且添加到该节点后面(被复制节点后面),第二次迭代把新节点random更新为node.random.next(新节点的random节点应该为旧节点random节点的下一个节点,即为被复制的节点),把random更新完后我们需要把新链表拆分出来并且维护旧链表

拆分新链表:

  1. p = head,创建一个新节点newNode用于保存新链表,最后输出newNode.next,创建当前指向节点cur,初始指向newNode,对p不为空进行迭代
  2. 让当前节点cur指向p.next,即cur.next = p.next
  3. cur节点后移 即cur = cur.next
  4. 这一步需要把老节点相互之间连接起来,即p.next = cur.next
  5. p指向下一个老节点位置,即p = cur.next

代码

class Solution {
    public Node copyRandomList(Node head) {
        //插入复制节点,更新next节点
        for(Node p=head;p!=null;p=p.next.next){
            Node node = new Node(p.val,p.next,null);
            p.next = node;
        }
        //更新random节点
        for(Node p=head;p!=null;p=p.next.next){
            if(p.random!=null)
                p.next.random = p.random.next;
        }
        //拆分新链表
        Node newNode = new Node(-1,null,null);
        Node p = head;
        Node cur = newNode;
        while(p!=null){
            cur.next = p.next;
            cur = cur.next;
            p.next = cur.next;//维护老链表
            p = cur.next;
        }
        return newNode.next;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/linkedlist-copy.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!