剑指Offer-面试题35-复杂链表的复制

2020-05-05

题目描述

请实现copyRandomList函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个next指针指向下一个节点，还有一个random指针指向链表中的任意节点或者null。

示例1：
示例1

1 2	输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例2：
示例2

1 2	输入：head = [[1,1],[2,1]] 输出：[[1,1],[2,1]]

示例3：
示例3

1 2	输入：head = [[3,null],[3,0],[3,null]] 输出：[[3,null],[3,0],[3,null]]

示例4：

1
2
3

输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。

提示：

-10000 <= Node.val <= 10000
Node.random为空(null)或指向链表中的节点
节点数目不超过1000

思路

第一次遍历链表，在原节点的后面复制一个一样的节点
第二次遍历链表，为复制的节点设置对应的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) {
        //若链表为空，则返回null
        if(head == null){
            return null;
        }
        //在原节点后复制一个一样的节点
        Node cur = head;    
        //第一次遍历
        while(cur != null){
            Node nex = cur.next;
            Node node = new Node(cur.val);  //创建一个新节点，值为原节点
            //将复制的新节点链接到原节点后面
            cur.next = node;
            node.next = nex;
            //当前节点后移
            cur = nex;
        }
        //为复制的节点设置random
        cur = head;
        //第二次遍历
        while(cur != null){
            if(cur.random == null){ //若当前节点的random为空，则后面的复制节点的random也空
                cur.next.random = null;
            }
            else{   //否则复制节点的random就是当前节点的random的下一个
                cur.next.random = cur.random.next;
            }
            //当前节点后移两位（因为后一位是复制节点）
            cur = cur.next.next;
        }
        //将复制的节点从链表中分离出来
        cur = head;
        Node cloneHead = cur.next;  //复制节点的头节点
        //第三次遍历
        while(cur != null){
            Node clone = cur.next;
            cur.next = clone.next;
            //如果复制节点的下一个不为空（即还有原节点）
            if(clone.next != null){
                clone.next = clone.next.next;
            }
            //为空
            else{
                clone.next = null;
            }
            //当前节点后移
            cur = cur.next;
        }
        return cloneHead;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。