Leetcode刷题java之138. 复制带随机指针的链表（一天一道编程题之第十五天）

青旅半醒 2023-07-11 15:05 18阅读 0赞

执行结果：

通过

显示详情

执行用时 :0 ms, 在所有 Java 提交中击败了100.00% 的用户

内存消耗 :41.1 MB, 在所有 Java 提交中击败了5.05%的用户

题目：

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

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

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 \[val, random\_index\] 表示：

val：一个表示 Node.val 的整数。  
random\_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

包含三个部分，复制，随机，拆分。

代码：

/*
    // Definition for a Node.
    class Node {
        int val;
        Node next;
        Node random;
    
        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    */
    class Solution {
        public Node copyRandomList(Node head) {
            if(head==null)
            {
                return null;
            }
            Node cur1=head;
            //复制
            while(cur1!=null)
            {
                Node temp1=new Node(cur1.val);
                temp1.next=cur1.next;
                cur1.next=temp1;
                cur1=temp1.next;
            }
            //随机指向
            Node cur2=head;
            while(cur2!=null)
            {
                Node temp2=cur2.next;
                if(cur2.random!=null)
                {
                    temp2.random=cur2.random.next;
                }
                cur2=temp2.next;
            }
            //拆分
            Node cur3=head;
            Node result=head.next;
            while(cur3.next!=null)
            {
                Node temp3=cur3.next;
                cur3.next=temp3.next;
                cur3=temp3;
            }
            return result;
        }
    }