【剑指offer】复杂链表的复制

菜鸡膜拜ORZ

// 剑指offer书上方法1：巧妙的运用哈希表在O(1)的时间对每个节点找到了random值。
public class Solution {

    private Map<RandomListNode, RandomListNode> map = new HashMap<>();

    public RandomListNode CloneNext(RandomListNode pHead) {
        RandomListNode copyHead = new RandomListNode(pHead.label);
        RandomListNode copyNode = copyHead;
        map.put(pHead, copyHead);
        while (pHead.next != null) {
            pHead = pHead.next;
            copyNode.next = new RandomListNode(pHead.label);
            copyNode = copyNode.next;
            map.put(pHead, copyNode);
        }
        return copyHead;
    }

    public RandomListNode CloneRandom(RandomListNode listNode, RandomListNode pHead) {
        RandomListNode copyHead = listNode;
        while (pHead != null) {
            if (pHead.random != null) {
                listNode.random = map.get(pHead.random);
            }
            pHead = pHead.next;
            listNode = listNode.next;
        }
        return copyHead;
    }

    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode copyList = CloneNext(pHead);
        copyList = CloneRandom(copyList, pHead);
        return copyList;
    }
}

// 剑指offer书上方法2：第一步、第二步、第三部 ORZ
public class Solution {

    public void CloneNodes(RandomListNode pHead) {
        RandomListNode nextNode;
        while (pHead != null) {
            nextNode = pHead.next;
            pHead.next = new RandomListNode(pHead.label);
            pHead = pHead.next;
            pHead.next = nextNode;
            pHead = nextNode;
        }
    }

    public void CloneRandom(RandomListNode pHead) {
        while (pHead != null) {
            if (pHead.random != null) {
                pHead.next.random = pHead.random.next;
            }
            pHead = pHead.next.next;
        }
    }

    public RandomListNode SplitList(RandomListNode pHead) {
        RandomListNode copyNode = pHead.next, copyHead = copyNode, tmpNode = copyNode.next;
        while (tmpNode != null) {
            pHead.next = tmpNode;
            pHead = pHead.next;
            copyNode.next = tmpNode.next;
            copyNode = copyNode.next;
            tmpNode = tmpNode.next.next;
        }
        pHead.next = null;
        return copyHead;
    }

    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        CloneNodes(pHead);
        CloneRandom(pHead);
        return SplitList(pHead);
    }
}