剑指Offer（二十五）复杂链表的复制（Java版 )

灰太狼 2021-09-26 23:14 181阅读 0赞

# 一、题目描述 #

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

# 二、代码描述 #

/* public class RandomListNode { int label; RandomListNode next = null; RandomListNode random = null; RandomListNode(int label) { this.label = label; } } */
    public class Solution {
        public RandomListNode Clone(RandomListNode pHead){
            if(pHead==null)
                return null;
            //将头结点保存下来
            RandomListNode pCur = pHead;
            //第一步：复制next 如原来是A->B->C 变成A->A'->B->B'->C->C'
            while(pCur!=null){
                //创建一个节点，值为头结点的值
                RandomListNode node = new RandomListNode(pCur.label);
                //头节点的下一个节点
                node.next = pCur.next;
                //头结点的下一个结点为node
                pCur.next = node;
                //pCur指向下一个结点
                pCur = node.next;
            }
    
            //第二步
            pCur = pHead;
            //复制random pCur是原来链表的结点 pCur.next是复制pCur的结点
            while(pCur!=null){
                if(pCur.random!=null)
                    pCur.next.random = pCur.random.next;
                pCur = pCur.next.next;
            }
    
            //第三步 将链表拆分为两个链表
            RandomListNode head = pHead.next;//复制链表的头结点
            RandomListNode cur = head;//偶数位置为复制链表
            pCur = pHead;//奇数位置为原链表
            //拆分链表
            while(pCur!=null){
                pCur.next = pCur.next.next;
                if(cur.next!=null)//注意最后一个复制节点的时候就没有next的next
                    cur.next = cur.next.next;
                cur = cur.next;
                pCur = pCur.next;
            }
            return head;       
        }
    }

运行结果：  
![这里写图片描述][70]

[70]: /images/20210923/5216baaffb974f1c9a68558204274eca.png