剑指offer - 复杂链表的复制(Java实现)

题目链接：https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&&tqId=11178&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：首先我们先遍历链表，然后将链表先复制一次，并且使用 next 将他们连接起来，这样我们就得到了一个链表。其次我们需要将其 random 指针指向的节点连接到链表上面。首先我们可以考虑暴力的情况，我们遍历原始的链表，看看当前节点 random 指向的节点距离头结点有多少步，通过这个步数，我们就可以在复制的链表中找到这个节点，然后让当前节点的 random 指向我们找到的节点即可。时间复杂度

/*  
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return pHead;
        RandomListNode clone = copy(pHead);
        clone = findRandom(pHead, clone);
        return clone;
    }
    public static RandomListNode findRandom(RandomListNode pHead, RandomListNode clone) {
        RandomListNode curNode = pHead, curCloneNode = clone;
        RandomListNode randomNode = pHead, randomCloneNode = clone;
        while(curNode != null) {
            int step = 0;
            if(curNode.random != null) {//找到原始链表中的random指向的节点
                while(randomNode != curNode.random) {
                    ++ step;
                    randomNode = randomNode.next;
                }
                while(step > 0) {//找到复制链表中指向的节点
                    -- step;
                    randomCloneNode = randomCloneNode.next;
                }
                curCloneNode.random = randomCloneNode;
            }
            curNode = curNode.next;
            curCloneNode = curCloneNode.next;
            randomNode = pHead;
            randomCloneNode = clone;
        }
        return clone;
    }
    public static RandomListNode copy(RandomListNode pHead) {//链表的复制
        RandomListNode cur = pHead;
        RandomListNode q = new RandomListNode(-1), ans = q;
        while(cur != null) {
            RandomListNode cloneNode = new RandomListNode(cur.label);
            q.next = cloneNode;
            q = q.next;
            cur = cur.next;
        }
        return ans.next;
    }
}

  思路二：这种思路我们主要聚焦在怎么去优化找 random 指向的节点的。用下面的图来表示这种思路的一个存储方式：

  按照上图，我们可以发现，如果把原节点和复制节点的关系使用 Map 存储起来，那么我们在进行 random 节点的复制的时候就可以直接根据 Map 中的数据来进行赋值，这个复杂度为 。

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return pHead;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while(cur != null) {//存储节点关系
            RandomListNode cloneNode = new RandomListNode(cur.label);
            map.put(cur, cloneNode);
            cur = cur.next;
        }
        cur = pHead;
        while(cur != null) {//根据关系复制链表
            RandomListNode cloneNode = map.get(cur);
            cloneNode.next = map.get(cur.next);
            cloneNode.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}

  思路三：在原链表中一次插入复制的节点，建立关系后拆分链表。这里要注意最后的返回，由于后台判题的机制，我们需要进行一定的处理，否则字符串输出的就是空串。

  从上面的图可以看出来，我们不用使用Map就可以将其中的关系关联起来，进而进行一个复制，最后拆分这个链表即可。

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/
import java.util.*;

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) return null;
        RandomListNode cur = pHead;
        while(cur != null) {//向原链表中插入复制节点
            RandomListNode cloneNode = new RandomListNode(cur.label);
            cloneNode.next = cur.next;
            cur.next = cloneNode;
            cur = cloneNode.next;
        }

        cur = pHead;
        while(cur != null) {//根据位置关系求出复制节点相应的random
            if(cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        RandomListNode head = pHead.next;//拆分为两个链表
        cur = pHead;//要使用这种方式来进行拆分,不然会出现空串的情况
        while(cur.next != null) {
            RandomListNode temp = cur.next;
            if(temp != null) {
                cur.next = temp.next;
                cur = temp;
            }
        }
        return head;//输出复制链表
    }
}