复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判断程序会直接返回空）

两种策略解决

策略1（HashMap解决）

1. 先用一个HashMap的key存放原来的链表，value存放key的值。
2. 知道了key的指向，然后让value跟着key一样的指向即可。

代码

import java.util.HashMap;

/**
 * @author god-jiang
 * @date 2020/1/16  18:48
 */
public class RandomListNodeCopy {
    //定义复杂链表的结构
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = pHead;
        while (cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = pHead;
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(pHead);
    }
}

通过截图

HashMap解法总结

用HashMap做简单，容易理解，时间复杂度为O(N)，空间复杂度也为O(N)，其实这道题还可以做到时间复杂度为O(N)，空间复杂度为O(1)，就是我接下来介绍的这种解法。

---

策略2（创建拆分）

1. 遍历链表，复制每个节点，如复制节点A得到A1，将节点A1插到节点A后面
2. 重新遍历链表，复制旧节点的随机指针给新节点，如A1.random = A.random.next
3. 拆分链表，将链表拆分为原链表和复制后的链表

图解

代码

import java.util.HashMap;

/**
 * @author god-jiang
 * @date 2020/1/16  18:48
 */
public class RandomListNodeCopy {
    //定义复杂链表的结构
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

    //合并拆分的时间复杂度为O(N)，空间复杂度为O(1)
    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }

        RandomListNode cur = pHead;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while (cur != null) {
            RandomListNode cloneNode = new RandomListNode(cur.label);
            RandomListNode nextNode = cur.next;
            cur.next = cloneNode;
            cloneNode.next = nextNode;
            cur = nextNode;
        }

        cur = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        //3、拆分链表，将链表拆分为原链表和复制后的链表
        cur = pHead;
        RandomListNode pCloneHead = pHead.next;
        while (cur != null) {
            RandomListNode cloneNode = cur.next;
            cur.next = cloneNode.next;
            cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
            cur = cur.next;
        }
        return pCloneHead;
    }
}

通过截图

总结

一道好的题目往往有多种解决的办法，大二时期的我就只会用最基础的贪心和暴力解决各类问题，不是说暴力解法不好，只是有时候有更好的算法可以解决我们又为何不去掌握呢。所以一道题目的多种的解法我都会好好研读和学习。希望也有人喜欢和我一样多了解多种解法，扩展一下自己的思路，嘿嘿嘿。。。

PS：如果觉得博主写的不错的话可以点点赞，关注走一波，谢谢大家的支持了~~~