复杂链表的复制

这道题目我的解法没什么技术含量，就是暴力遍历，我的解法也没有使用哈希表，讲道理从工业代码开发的角度，Java哈希表中作为键的元素为了实现可比较，需要重写equals和hashCode方法，本题Java提交中那些使用哈希表的实现，直接将RandomListNode实例作为键，即使用HashMap能够AC这道题目，其实现对于实际工业开发没有任何借鉴意义。

• 第一遍，沿着next指针将整个链表的所有节点重建，相当于复制一遍主干线路。
• 第二遍，依次处理每个节点的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 oldHead) {
        if (oldHead == null) {
            return null;
        }
        // step 1 沿着next把整个主干线路复原
        RandomListNode newHead = new RandomListNode(oldHead.label);
        RandomListNode p0 = oldHead;
        RandomListNode p1 = newHead;
        while (p0.next != null) {
            p1.next = new RandomListNode(p0.next.label);
            p0 = p0.next;
            p1 = p1.next;
        }

        // step 2 挨个复原枝干线路
        RandomListNode p0cur = oldHead, p1cur = newHead, p0ran;
        while (p0cur != null) { // p0cur是每个处理的当前节点
            p0ran = p0cur.random;
            if (p0ran == null) {
                // 如果原节点的random是null,那么单独简单处理
                p1cur.random = null;
            } else {
                for (p0 = oldHead, p1 = newHead; p0 != null; p0 = p0.next, p1 = p1.next) {
                    // 暴力遍历，每次从头遍历，直到找到p0cur的random指向的节点，注意两个链表的同步性
                    if (p0 == p0ran) {
                        p1cur.random = p1;
                        break;
                    }
                }
            }
            p0cur = p0cur.next;
            p1cur = p1cur.next;
        }
        return newHead;
    }
}

后面再学习《剑指Offer》上的解法，大体是在旧链表中重建新链表，最后把旧链表和新链表拆分成2个独立的链表。

虽然我的解法是暴力解法，但是也能跑过80%的Java提交，不知道是不是牛客的案例太蒻的原因。

还是那个感受，刷题的步骤如下：

1. 别管自己的想法的效率如何，是否最优解，先想一个解法，然后动手实现，这个过程中不要参考任何现成解法或提交。
2. 自己第一版的实现AC后，再去分析第一版的实现，看是否存在优化的空间。
3. 对比他人的题解或提交，再分析自己的实现。
4. 没有一点思路的题目记录下来，看题解和别人的提交，自己理解后重复实现一下，也不要太过在意自己是否记住这道题的解法，以后针对这一类题目重复训练，慢慢的这一类题目就有思路了。

总结起来：

1. 一定要有自己的想法，哪怕自己的想法很弱鸡，也要有自己的解法，然后一定要实现自己的解法做到AC。
2. 在自己实现的基础上，与别人的提交或者最优解进行对比。
3. 如果实在没有想法，那这种题目就是知识盲点，那就要记录下来以后针对同类题目刻意训练。

为什么我这么强调自己的解法，就是因为不自己动手给答案撸出来，就会眼高手低，比如，看到一个题目，自己想了想，有了一个思路或者没有思路，然后就开始看题解，看别人的提交，看懂了之后把别人的提交复制过来，改吧改吧，AC了就觉得自己刷过了这道题。其实任何一门语言，从算法落地到数据结构和具体的实现的时候是有自己的特点的，这个特点是具体语言相关的，这个过程不去实践，真正到了写代码的时候是撸不出来的，也就是眼高手低，动手能力不行。

只有自己撸出来一发，然后去调试，AC，复盘，才能真正提升编码能力，体会算法和实现的具体细节，后续再与别人进行对比的时候，才能更深理解自己和别人的实现的优缺点。

总之，一定要有自己的解法，自己的实现，自己的AC，再去看别人的解，才能真正吸收一道题，一点思路没有的题，就是知识的盲点，以后要刻意训练，随着上述过程的不断迭代，就会发现一点思路没有的题越来越少，而已经做过的题，理解的越来越透彻。