/*******************************************************************
Copyright(c) 2016, Tyrone Li
All rights reserved.
*******************************************************************/
// 作者:TyroneLi
///*
Q:复制复杂链表。请实现函数complexListNode*clone(ComplexListNode*pHead)，复制一个复杂链表，在复杂链表中除了有m_pNext指针指向下一个节点的时候，还有一个m_pSibling指针指向链表中的任意一个结点或者NULL。
S:这里分三个步骤来做：1.先根据m_pNext指针复制每个结点，这里每个节点复制两次挨在一起，比如结点N复制得到结点N'，->N->N'->2.根据第一步每个N结点的m_pSibling指向S,那么可以得到N'的m_pSibling指针指向的S'结点3.此时可以根据把奇数位置的结点摘下来，然后就得到的是原链表；把偶数位置的结点摘下来便得到复制的链表。
*/#include "../utils/ComplexList.h"
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstdlib>void cloneNodes(ComplexListNode*pHead)
{if(pHead == nullptr)return;ComplexListNode*pNode = pHead;while(pNode != nullptr){ComplexListNode*pCopyNode = new ComplexListNode();pCopyNode->m_nValue = pNode->m_nValue;pCopyNode->m_pNext = pNode->m_pNext;pCopyNode->m_pSibling = pNode->m_pSibling;pNode->m_pNext = pCopyNode;pNode = pCopyNode->m_pNext;}
}void cloneSiblingNodes(ComplexListNode*pHead)
{if(pHead == nullptr)return;// printComplextList(pHead);ComplexListNode*pNode = pHead;while(pNode != nullptr){ComplexListNode*pCopyNode = pNode->m_pNext;if(pNode->m_pSibling != nullptr)pCopyNode->m_pSibling = pNode->m_pSibling->m_pNext;pNode = pCopyNode->m_pNext;}
}ComplexListNode*sliceComplexList(ComplexListNode*pHead)
{if(pHead == nullptr)return nullptr;ComplexListNode*pNode = pHead;ComplexListNode*pCopyHead = nullptr;ComplexListNode*pCopyNode = nullptr;if(pNode != nullptr){pCopyHead = pCopyNode = pNode->m_pNext;pNode->m_pNext = pCopyNode->m_pNext;pNode = pNode->m_pNext;}while(pNode != nullptr){pCopyNode->m_pNext = pNode->m_pNext;pCopyNode = pCopyNode->m_pNext;pNode->m_pNext = pCopyNode->m_pNext;pNode = pNode->m_pNext;}return pCopyHead;
}ComplexListNode*getCopyComplexList(ComplexListNode*pHead)
{if(pHead == nullptr)return nullptr;cloneNodes(pHead);cloneSiblingNodes(pHead);return sliceComplexList(pHead);
}void test_1()
{std::cout << "Test 1, normal.";ComplexListNode*pNode1 = createComplexListNode(1);ComplexListNode*pNode2 = createComplexListNode(2);ComplexListNode*pNode3 = createComplexListNode(3);ComplexListNode*pNode4 = createComplexListNode(4);ComplexListNode*pNode5 = createComplexListNode(5);connectComplexListNodes(pNode1, pNode2, pNode3);connectComplexListNodes(pNode2, pNode3, pNode5);connectComplexListNodes(pNode3, pNode4, nullptr);connectComplexListNodes(pNode4, pNode5, pNode2);printComplextList(pNode1);ComplexListNode*copyList = getCopyComplexList(pNode1);printComplextList(copyList);
}void test_2()
{std::cout << "Test 2, cycle.";ComplexListNode*pNode1 = createComplexListNode(1);ComplexListNode*pNode2 = createComplexListNode(2);ComplexListNode*pNode3 = createComplexListNode(3);ComplexListNode*pNode4 = createComplexListNode(4);ComplexListNode*pNode5 = createComplexListNode(5);connectComplexListNodes(pNode1, pNode2, nullptr);connectComplexListNodes(pNode2, pNode3, pNode5);connectComplexListNodes(pNode3, pNode4, pNode3);connectComplexListNodes(pNode4, pNode5, pNode2);printComplextList(pNode1);ComplexListNode*copyList = getCopyComplexList(pNode1);printComplextList(copyList);
}void test_3()
{std::cout << "Test 3, one node.";ComplexListNode*pNode1 = createComplexListNode(1);printComplextList(pNode1);ComplexListNode*copyList = getCopyComplexList(pNode1);printComplextList(copyList);
}void test_getComplexList()
{test_1();test_2();test_3();
}int main(int argc, char**argv)
{test_getComplexList();return 0;
}