题目:请实现函数ComplexListNode* clone(ComplexListNode* pHead),复制
一个复杂链表。在复杂链表中,每个节点除了有一个m_pNext指针指向下一个
节点外,还有以一个m_pSibling指向链表中的任意节点或者NULL。节点定义如下:
在complexList.h中定义
#pragma once struct ComplexListNode { int m_nValue; ComplexListNode* m_pNext; ComplexListNode* m_pSibling; }; ComplexListNode* CreateNode(int nValue); void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling); void PrintList(ComplexListNode* pHead);在complexLish.cpp中实现上面的三个基本操作
#include"complexList.h" #include "stdio.h" ComplexListNode* CreateNode(int nValue) { ComplexListNode* pNode = new ComplexListNode(); pNode->m_nValue = nValue; pNode->m_pNext = NULL; pNode->m_pSibling = NULL; return pNode; } void BuildNodes(ComplexListNode* pNode, ComplexListNode* pNext, ComplexListNode* pSibling) { if(pNode != NULL) { pNode->m_pNext = pNext; pNode->m_pSibling = pSibling; } } void PrintList(ComplexListNode* pHead) { ComplexListNode* pNode = pHead; while(pNode != NULL) { printf("The value of this node is: %d.\n", pNode->m_nValue); if(pNode->m_pSibling != NULL) printf("The value of its sibling is: %d.\n", pNode->m_pSibling->m_nValue); else printf("This node does not have a sibling.\n"); printf("\n"); pNode = pNode->m_pNext; } }在实现ComplexListNode* clone(ComplexListNode* pHead)源文件中实现该方法并作测试
#include#include"complexList.h" //复制原始链表的任意节点N并创建新节点N',再把N'连接到N的后面。 void cloneNodes(ComplexListNode* pHead) { if(pHead == NULL) return; ComplexListNode* pNode = pHead; while(pNode != NULL) { ComplexListNode* pCloned = new ComplexListNode(); pCloned->m_pNext = pNode->m_pNext; pCloned->m_nValue = pNode->m_nValue; pCloned->m_pSibling = NULL; pNode->m_pNext = pCloned; pNode = pNode->m_pNext; } } //如果原始链表上的节点N的m_pSibling指向,则它对应的复制节点 //N'的m_pSibling指向S的下一节点S'。 void connectSiblingNodes(ComplexListNode* pHead) { if(pHead == NULL) return; ComplexListNode* pNode = pHead; while(pNode != NULL) { if(pNode->m_pSibling) { pNode->m_pNext->m_pSibling = pNode->m_pSibling->m_pNext; } pNode = pNode->m_pNext; } } //将上面两步得到的表拆分成两个链表 ComplexListNode* reconnectNodes(ComplexListNode* pHead) { ComplexListNode* pNode = pHead; ComplexListNode* pCLonedHead = NULL; ComplexListNode* pClonedNode = NULL; if(pHead) { pCLonedHead = pClonedNode = pNode->m_pNext; pNode->m_pNext = pClonedNode->m_pNext; pNode = pNode->m_pNext; } while(pNode != NULL) { pClonedNode->m_pNext = pNode->m_pNext; pNode->m_pNext = pClonedNode->m_pNext; pNode = pNode->m_pNext; pClonedNode = pClonedNode->m_pNext; } return pCLonedHead; } ComplexListNode* clone(ComplexListNode* pHead) { cloneNodes(pHead); reconnectNodes(pHead); return reconnectNodes(pHead); } void test() { ComplexListNode* pNode1 = CreateNode(1); ComplexListNode* pNode2 = CreateNode(2); ComplexListNode* pNode3 = CreateNode(3); ComplexListNode* pNode4 = CreateNode(4); ComplexListNode* pNode5 = CreateNode(5); BuildNodes(pNode1, pNode2, pNode3); BuildNodes(pNode2, pNode3, pNode5); BuildNodes(pNode3, pNode4, NULL); BuildNodes(pNode4, pNode5, pNode2); printf("The original list is:\n"); PrintList(pNode1); ComplexListNode* pClonedHead = clone(pNode1); printf("The cloned list is:\n"); PrintList(pClonedHead); } int main() { test(); }