题目:复杂链表的复制

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

 

 

图片来自于:https://www.cnblogs.com/edisonchou/p/4790090.html  写得不错,只不过是用C++写的

 

下面来分析不借助辅助空间的O(n)解法

首先这是初始的复杂链表

 把所有的链表节点复制一遍,对<另一个特殊指针指向任意一个节点>先不操作

对<另一个特殊指针指向任意一个节点>进行复制

然后拆开

 

 

 1 /*
 2 public class RandomListNode {
 3     int label;
 4     RandomListNode next = null;
 5     RandomListNode random = null;
 6 
 7     RandomListNode(int label) {
 8         this.label = label;
 9     }
10 }
11 */

 

 1 public class Solution {
 2     public RandomListNode Clone(RandomListNode pHead) {
 3         //考虑特殊情况
 4         if(pHead == null) {
 5             return null;
 6         }
 7         RandomListNode currentNode = pHead;
 8         //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
 9         //虽然过程有点绕,但是在纸上写一写还是能弄明白的
10         while(currentNode != null){
11             RandomListNode cloneNode = new RandomListNode(currentNode.label);
12             RandomListNode nextNode = currentNode.next;
13             currentNode.next = cloneNode;
14             cloneNode.next = nextNode;
15             currentNode = nextNode;
16         }
17         currentNode = pHead;
18         //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
19         while(currentNode != null) {
20             //? :语句先计算出来结果,然后赋值,比if else要强
21             currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
22             currentNode = currentNode.next.next;
23         }
24         //3、拆分链表，将链表拆分为原链表和复制后的链表
25         currentNode = pHead;
26         //这个pCloneHead节点就是用来返回的,后期拆分操作肯定不会动头节点的
27         RandomListNode pCloneHead = pHead.next;
28         while(currentNode != null) {
29             RandomListNode cloneNode = currentNode.next;
30             currentNode.next = cloneNode.next;
31             cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
32             currentNode = currentNode.next;
33         }
34         return pCloneHead;
35     }
36 }

 总得来说,起初理解这道题的时候有些费劲,连题目也没有看懂;

在链表的拆拆合合中,也搞不清楚方向,总之还是需要多加练习