[Leetcode LCR 154][Medium]-复杂链表的复制-链表

目录

一、题目描述

二、整体思路

三、代码

一、题目描述

原题地址

二、整体思路

        这道题难点在于如何处理random。因为涉及到的所有节点都在同一链表，因此可以在链表上利用复制-拆分的方法去做。

        先在链表上把每个节点复制自身一次，相当于cur与cur.next中间插入一个val与cur.val相同的新节点。

        然后再复制random，从头遍历链表，cur.next是复制的新节点,cur.next.random=cur.random.next。遍历完的同时random也复制好了。注意不能cur.next.random=cur.random。因为这样的话就拆分不了链表了。

        最后再拆分链表。

三、代码

/*
// 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 cur=head;//复制节点(只复制next)
        while(cur!=null){
            Node nxt=cur.next;
            cur.next=new Node(cur.val);
            cur.next.next=nxt;
            cur=nxt;
        }
        cur=head;
        while(cur!=null){//复制random
            cur.next.random=cur.random==null ? null : cur.random.next;
            cur=cur.next.next;
        }
        cur=head;
        Node res=cur.next;//拆分
        Node temp=res;
        while(cur!=null){
            cur.next=cur.next==null ? null : cur.next.next;
            temp.next=temp.next==null ? null :temp.next.next;
            cur=cur.next;
            temp=temp.next;
        }
        return res;
    }
}