剑指offer：复杂链表的复制

今天药忘吃喽~ 2021-06-24 16:09 368阅读 0赞

**试题：**  
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）  
**代码：**  
这题关键是由于random是随机指向（可能指向前也可能指向后），这就要求我们先把链表复制出来，然后在重新为random指向。问题是如果把链表单独复制出来，我们就失去了相对关系。所以：  
1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面  
2、遍历链表，A1->random = A->random->next;  
3、将链表拆分成原链表和复制后的链表

/*
    public class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;
    
        RandomListNode(int label) {
            this.label = label;
        }
    }
    */
    public class Solution {
        public RandomListNode cHead = null;
        public RandomListNode Clone(RandomListNode pHead)
        {
            if(pHead == null) return null;
            
            RandomListNode tHead = pHead;
            RandomListNode temp = null;
            while(tHead != null){
                temp = new RandomListNode(tHead.label);
                temp.next = tHead.next;
                tHead.next = temp;
                tHead = temp.next;
            }
            tHead = pHead;
            while(tHead != null){
                temp = tHead.next;
                if(tHead.random != null){
                    temp.random = tHead.random.next;
                }
                tHead = temp.next;
            }
            tHead = pHead;
            cHead = tHead.next;
            while(tHead != null){
                temp = tHead.next;
                tHead.next = temp.next;
                tHead = tHead.next;
                temp.next = tHead==null?null:tHead.next;
            }
            return cHead;
        }
    }