剑指offer（二十五）复杂链表的复制

点击进入 牛客网题库：复杂链表的复制

题目描述

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

方法一

方法一，就是通过两个ArrayList然后把 原始链表和新链表都存起来，然后进行查看有 原始链表保存的 ArrayList的映射到 新链表， random这种，然后进行获取，最终返回回去

//代码丢失了，后续有时间的时候补上

方法二

public class Solution {
     public RandomListNode Clone(RandomListNode pHead) { 
        RandomListNode tmpNode1 = pHead;
        RandomListNode tmpNode2 = pHead;

        RandomListNode tmpNode = pHead;

        /**
         *创建一个新的节点然后进行拼接
         * tmpNode: 1-> 2-> 3-> 4-> 5
         *转变成
         * tmpNode: 1-> 1'->2-> 2'-> 3 ->3'-> 4->4'-> 5->5'
         * 
         */
        while(tmpNode != null) {
            
            //创建 1'
            RandomListNode n = new RandomListNode(tmpNode.label);
            //保存 1-> 2的 2 节点
            RandomListNode a = tmpNode.next;
            //使得 1'-> 2 
            n.next = a;
            //使得 1-> 1'
            tmpNode.next = n;
            //循环继续 tmpNode = 2的指向
            tmpNode = a;
        }

        /**
         * 把对应1' 等的random 串起来
         * ------------------
         * |                |
         * 1-> 1'->2-> 2'-> 3 ->3'-> 4->4'-> 5->5'
         * 
         * ------------------
         * |                |   
         * 1-> 1'->2-> 2'-> 3 ->3'-> 4->4'-> 5->5'
         *     |                | 
         *     ------------------
         * 
         * 就是说 1（random） -> 3
         * 通过这个方法后
         *       1'（random） -> 3'
         * 
         */
        while(tmpNode1 != null) {
            if(tmpNode1.random != null) {
                RandomListNode n = tmpNode1.next;
                n.random = tmpNode1.random.next;
            }
            //直接找下一个原链表的 random 进行判断
            //把1'等random赋值上去
            tmpNode1 = tmpNode1.next.next;
        }


        RandomListNode node = new RandomListNode(0);
        //复用上上次的tmpNode的声明，其实可以重写弄个别名，只是不想重新弄一个新名字
        tmpNode = node;

        pHead = tmpNode2;
        /**
         * 
         * 把处理的这个条链，拆分开来
         * 然后还原原始的链条(1->2...)，
         * 并且还要输出需要的的链条 （1'->2'...）
         * 
         * tmpNode: 1-> 1'->2-> 2'-> 3 ->3'-> 4->4'-> 5->5'
         * 
         * node :  1'->2'->3'->4'->5'
         * 
         * 要把pHead还原上，不然不通过
         * pHead: 1-> 2 -> 3 -> 4 -> 5
         *
         */
        while(tmpNode2 != null) {
            tmpNode.next = tmpNode2.next;
            tmpNode = tmpNode.next;
            
            tmpNode2 = tmpNode2.next.next;
            pHead.next = tmpNode2;
            pHead = pHead.next;
           
        }

        return node.next;
        
    }
}