【剑指offer】面试题35：复杂链表的复制

朱雀 2022-04-10 13:29 183阅读 0赞

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

牛客网链接：[https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba][https_www.nowcoder.com_questionTerminal_f836b2c43afc4b35ad6adc41ec941dba]

本题目是一个比较复杂的问题，需要拆解为几个子问题，分别实现函数。

具体分为三步：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

/**
     * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
     * 返回结果为复制后复杂链表的head。
     * （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
     * 
     * 解题思路：
     * 1、遍历链表，复制每个节点，如：复制节点A得到A1，将节点A1插到节点A后；
     * 2、重新遍历链表，复制老节点的随机指针给新结点，如：A1.random = A.random.next
     * 3、拆分链表，将链表拆分为原链表和复制后的链表
     */
    public class CopyComplexLinkedList {
    
    	public class RandomListNode{
    		int label;
    		RandomListNode next = null;
    		RandomListNode random = null;
    		
    		RandomListNode(int label){
    			this.label = label;
    		}
    	}
    	
    	public RandomListNode Clone(RandomListNode pHead){
    		if(pHead == null){
    			return null;
    		}
    		
    		RandomListNode currentNode = pHead;
    		
    		// 1、复制每个节点，如：复制节点A得到A1，将节点A1插到节点A后
    		while(currentNode != null){
    			RandomListNode cloneNode = new RandomListNode(currentNode.label);
    			// nextNode 为原 A 的后继节点
    			RandomListNode nextNode = currentNode.next;
    			// 将 A1 设置成 A 的后继节点
    			currentNode.next = cloneNode;
    			// 将原 A 的后继节点设置为 A1 的后继节点
    			cloneNode.next = nextNode;
    			// 遍历下一个节点
    			currentNode = nextNode;
    		}
    		
    		currentNode = pHead;
    		// 2、重新遍历链表，复制老节点的随机指针给新结点，如：A1.random = A.random.next
    		while(currentNode != null){
    			// A1.random = A.random.next
    			currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
    			// 因为从 A -> B,中间多了个 A1，多以要两个 next
    			currentNode = currentNode.next.next;
    		}
    		
    		// 3、拆分链表，将链表拆分为原链表和复制后的链表
    		currentNode = pHead;
    		// 复制链表的头节点
    		RandomListNode pCloneHead = pHead.next;
    		while(currentNode != null){
    			// cloneNode 是 currentNode 的后继节点
    			RandomListNode cloneNode = currentNode.next;
    			// 原链表中currentNode 的后继节点是符合链表中 cloneNode 的后继节点
    			currentNode.next = cloneNode.next;
    			// 复制链表 cloneNode 的后继节点是符合链表中 cloneNode 的cloneNode.next.next节点
    			cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
    			currentNode = currentNode.next;
    		}
    		return pCloneHead;
    	}
    }

[https_www.nowcoder.com_questionTerminal_f836b2c43afc4b35ad6adc41ec941dba]: https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220328/36a3b3ce71704c93b2537fbb04e9d287.png