剑指offer--分解让问题更简单

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

分析：

解题思路：
1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
3、拆分链表，将链表拆分为原链表和复制后的链表

image.png

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

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


解题思路：
1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
3、拆分链表，将链表拆分为原链表和复制后的链表
![image.png](https://img.haomeiwen.com/i6021048/805a95b7836f99d7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)


public class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if(pHead == null) return null;
        RandomListNode curNode = pHead;
        //1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while(curNode != null){
            RandomListNode cloneNode = new RandomListNode(curNode.label);
            cloneNode.next = curNode.next;
            curNode.next = cloneNode;
            curNode = cloneNode.next;
        }
        
        //2、重新遍历链表，复制老节点的随机节点给新节点
        curNode = pHead;
        while(curNode != null){
            RandomListNode cloneNode = curNode.next;
            cloneNode.random = curNode.random == null?null:curNode.random.next;
            curNode = curNode.next.next;
        }
        
        //3、拆分链表，将链表拆分为原链表和拆分后的链表
        curNode = pHead;
        RandomListNode pcloneHead = pHead.next;
        while(curNode != null){
            RandomListNode cloneNode = curNode.next;
            curNode.next = cloneNode.next;
            cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
            curNode = curNode.next;
        }
        return pcloneHead;
    }
}

方法二
分析：
1、创建一个Map ，用于保存 原链表的 每个节点 和其对应的 复制节点
2、将原链表的关系 赋予 复制节点的关系

/**
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
 
    RandomListNode(int label) {
        this.label = label;
    }
}
*/
class Solution {
    public RandomListNode Clone(RandomListNode pHead)
    {
        if (pHead == null) {
            return pHead;
        }
        RandomListNode p1 = pHead;
        RandomListNode p2 = pHead;
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        while (p1 != null) {
            map.put(p1, new RandomListNode(p1.label));
            p1 = p1.next;
        }
 
        while (p2 != null) {
            if (p2.next != null) {
                map.get(p2).next = map.get(p2.next);
            } else {
                map.get(p2).next = null;
            }
            map.get(p2).random = map.get(p2.random);
            p2 = p2.next;
        }
        return map.get(pHead);
    }
}