[每日一道小算法（五十一）] [链表]复杂链表的复制（剑指offer习题）

我会带着你远行 2023-07-06 14:37 39阅读 0赞

前言：  
链表的题，指针一定区分好，要不太容易出错了。

### 题目描述 ###

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

### 解题思路 ###

这一道题，想了好久也没想出来该怎么解决。最后直接采用直接复制的方法，采用map存储旧节点和新节点之间的映射关系。如果节点已经存在那么使用存在的节点即可，如果不存在那么需要新开辟节点并存储他们之间的映射关系。

### 代码样例 ###

package com.asong.leetcode.CloneList;
    
    import java.util.HashMap;
    
    /** * 复杂链表的复制 * 思路：使用map来存储映射关系。 */
    public class Solution1 { 
        public RandomListNode Clone(RandomListNode pHead)
        { 
            if(pHead == null)
            { 
                return null;
            }
            RandomListNode newHead = null;
            RandomListNode pPre = pHead;
            RandomListNode pClone = null;
            HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
            while(pPre!=null)
            { 
                if(newHead == null)
                { 
                    newHead = new RandomListNode(pPre.label);
                    pClone = newHead;
                    map.put(pHead,newHead);//保存映射关系
                }else { 
                    //先保存下一结点的值
                    if (pPre.next!=null && map.containsKey(pPre.next))
                    { 
                        pClone.next = map.get(pPre.next);
                    }else { 
                        if(pPre.next!=null)
                        { 
                            RandomListNode temp = new RandomListNode(pPre.next.label);
                            map.put(pPre.next,temp);
                            pClone.next = temp;
                        }
                    }
                    if(pPre.random!=null && map.containsKey(pPre.random))
                    { 
                        pClone.random = map.get(pPre.random);
                    }else { 
                        if(pPre.random!=null)
                        { 
                            RandomListNode temp = new RandomListNode(pPre.random.label);
                            map.put(pPre.random,temp);
                            pClone.random = temp;
                        }
                    }
                    pPre = pPre.next;
                    pClone = pClone.next;
                }
            }
    
            return newHead;
        }
    }