剑指offer-复杂链表的复制

题目描述

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

方法一：首先建立一个新链表，并处理链表的next结点；然后逐个结点查找链表的random结点，时间复杂对为O(n²);

 1 public RandomListNode Clone(RandomListNode pHead)
 2     {//链表 my
 3         RandomListNode head = new RandomListNode(0);
 4         RandomListNode pre = head;
 5         RandomListNode cur =null;
 6         RandomListNode pCur = pHead;
 7         //构建链表及next
 8         while(pCur!=null){
 9             cur = new RandomListNode(pCur.label);
10             pre.next = cur;
11             pre = pre.next;
12             pCur = pCur.next;
13         }
14         //构建链表random
15         pCur = pHead;//原链表遍历
16         cur = head.next;
17         while(pCur!=null){
18             RandomListNode random = pCur.random;
19             if(random!=null){
20                 RandomListNode randompCur =pHead;
21                 RandomListNode randomCur = head.next;
22                 while(randompCur!=null){
23                     if(randompCur==random){
24                         cur.random = randomCur;
25                         break;
26                     }
27                     randompCur = randompCur.next;
28                     randomCur = randomCur.next;
29                 }
30             }
31             pCur = pCur.next;
32             cur = cur.next;
33         }
34         return head.next;
35     }

方法二：首先在旧链表中创建新链表，在每个结点后插入一个复制结点；然后处理每个结点的random指针；最后拆分链表。时间复杂对为O(n);

 1 public RandomListNode Clone(RandomListNode pHead)
 2     {//链表 mytip
 3         RandomListNode head = new RandomListNode(0);
 4         RandomListNode cur =null;
 5         RandomListNode pCur = pHead;
 6         //遍历链表，在每个结点pCur后面插入pCur的复制结点cur
 7         while(pCur!=null){
 8             cur = new RandomListNode(pCur.label);
 9             cur.next = pCur.next;
10             pCur.next = cur;
11             pCur = cur.next;
12         }
13         //遍历链表，复制每个结点pCur的random指针
14         pCur = pHead;
15         while(pCur!=null){
16             RandomListNode random = pCur.random;
17             if(random!=null){
18                 pCur.next.random = random.next;
19             }
20             pCur = pCur.next.next;
21         }
22         //拆分链表
23         pCur = pHead;
24         cur = head;
25         while(pCur!=null){
26             cur.next = pCur.next;
27             cur = cur.next;
28             pCur.next = cur.next;
29             pCur = pCur.next;
30         }
31         return head.next;
32     }