算法题26 复杂链表的复制

题目

　　请实现函数 ComplexListNode clone(ComplexListNode head)，复制一个复杂链表。在复杂链表中，每个结点除了有一个 next 域指向下一个结点外，还有一个 sibling 指向链表中的任意结点或者 null。

分析

　　解题参见http://wiki.jikexueyuan.com/project/for-offer/question-twenty-six.html

　　引用

　　图 4.8 是一个含有 5 个结点的复杂链表。图中实线箭头表示 next 指针，虚线箭头表示 sibling 指针。为简单起见，指向 null 的指针没有画出。

　　在不用辅助空间的情况下实现 O(n)的时间效率。

　　第一步：仍然是根据原始链表的每个结点N 创建对应的 N’。把 N’链接在N的后面。图 4.8 的链表经过这一步之后的结构，如图 4.9 所示。

　　第二步：设置复制出来的结点的 sibling。假设原始链表上的 N 的 sibling 指向结点 S，那么其对应复制出来的 N’是 N的 pext 指向的结点，同样 S’也是 S 的 next 指向的结点。设置 sibling 之后的链表如图 4.10 所示。

　　第三步：把这个长链表拆分成两个链表。把奇数位置的结点用 next 链接起来就是原始链表，把偶数位置的结点用 next 链接起来就是复制出来的链表。图 4.10 中的链表拆分之后的两个链表如图 4.11 所示。

代码

 1 struct CListNode
 2 {
 3     char value;
 4     CListNode* pNext;
 5     CListNode* pSibLing;
 6 };
 7 
 8 CListNode* CopyComplexList(CListNode* head)
 9 {
10     if (!head)
11     {
12         throw std::exception("Invalid Input.");
13     }
14 
15     CListNode* node=head;
16     while(node!=NULL)
17     {
18         CListNode* cnode=new CListNode();
19         cnode->value=node->value;
20         cnode->pNext=node->pNext;
21         node->pNext=cnode;
22         node=cnode->pNext;
23     }
24 
25     node=head;
26     CListNode* cnode;
27     while (node!=NULL)
28     {
29         cnode=node->pNext;
30 
31         if (node->pSibLing)
32         {
33             cnode->pSibLing=node->pSibLing->pNext;
34         }else
35         {
36             cnode->pSibLing=NULL;
37         }
38 
39         node=cnode->pNext;
40     }
41 
42     //split the list
43     node=head;
44     CListNode* chead=head->pNext;
45     while (node!=NULL)
46     {
47         cnode=node->pNext;
48 
49         node->pNext=cnode->pNext;
50         if (node->pNext)
51         {
52             cnode->pNext=node->pNext->pNext;
53         }else
54         {
55             cnode->pNext=NULL;
56         }
57 
58         node=node->pNext;
59     }
60 
61     return chead;
62 }