复杂链表的复制

有一个复杂链表，其结点除了有一个m_pNext指针指向下一个结点外，还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下：

struct ListNode
{
    int value;
    ListNode *next;
    ListNode *sibling;    
};

下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示m_pNext指针，虚线箭头表示m_pSibling指针。为简单起见，指向NULL的指针没有画出。

程序员面试题精选100题(49)-复杂链表的复制 - 何海涛 - 微软、Google等面试题

完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。

第一步根据原始链表的每个结点N，创建对应的N’。这一次，我们把N’链接在N的后面。实例中的链表经过这一步之后变成了：

代码如下：

 1 void clone(ListNode *pHead)
 2 {
 3     ListNode *pNode = pHead;
 4 
 5     while(pNode!=NULL)
 6     {
 7         //  创建对应的N'结点
 8         ListNode *pClone = new ListNode;
 9         pClone->value = pNode->value;
10         pClone->next = pNode->next;
11         pClone->sibling = NULL;
12 
13         pNode->next = pClone;
14         pNode = pClone->next;
15     }
16 }

第二步是设置我们复制出来的链表上的结点的m_pSibling。我们在上一步中把每个结点复制出来的结点链接在原始结点后面，有了这样的链接方式，我们就能在O(1)中就能找到每个结点的m_pSibling了。例子中的链表经过这一步，就变成如下结构了：

代码如下：

 1 void connectSibling(ListNode *pHead)
 2 {
 3     ListNode *pNode = pHead;
 4     while(pNode!=NULL)
 5     {
 6         ListNode *p = pNode->next;
 7         if(pNode->sibling)
 8             p->sibling = pNode->sibling->next;
 9         pNode = p->next;
10     }
11 }

第三步是把这个长链表拆分成两个。上述例子中的链表拆分之后的两个链表如下：

代码如下：

 1 ListNode *split(ListNode *pHead)
 2 {
 3     ListNode *pNode = pHead;
 4     ListNode *pCloneHead = NULL;
 5     ListNode *pCloneNode = NULL;
 6     if(pNode!=NULL)
 7     {
 8         pCloneHead = pCloneNode = pNode->next;
 9         pNode->next = pCloneNode->next;
10         pNode = pNode->next;
11     }
12     while(pNode!=NULL)
13     {
14         pNode->next = pCloneNode->next;
15         pNode = pNode->next;
16 
17         pCloneNode->next = pNode->next;
18         pCloneNode = pCloneNode->next;
19     }
20     return pCloneHead;
21 }

把上面三步合起来，就是复制链表的完整过程:

1 ListNode *Clone(ListNode *pHead)
2 {
3     clone(pHead);
4     connectSibling(pHead);
5     return split(pHead);
6 }

转载自：http://zhedahht.blog.163.com/。