题解 | #复杂链表的复制#
复杂链表的复制
https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba
/* struct RandomListNode { int label; struct RandomListNode *next, *random; RandomListNode(int x) : label(x), next(NULL), random(NULL) { } }; */ class Solution { public: RandomListNode* Clone(RandomListNode* pHead) { // 空的判断 if (pHead == nullptr) return nullptr; int listLen; RandomListNode* pReHead = new RandomListNode(pHead->label); RandomListNode* pInCurr = pHead; RandomListNode* pReCurr = pReHead; // 先复制主干next 上的 pInCurr = pInCurr->next; for (listLen = 0; pInCurr != nullptr; listLen++) { pReCurr->next = new RandomListNode(pInCurr->label); pInCurr = pInCurr->next; pReCurr = pReCurr->next; } // 再复制跳跃的 int value; pInCurr = pHead; pReCurr = pReHead; RandomListNode* pReScan = pReHead; for (int i = 0; i < listLen ; i++ ) { if (pInCurr->random != nullptr) { // 将输出的扫描指针归位 pReScan = pReHead; // 提取出对应节点的值 value = pInCurr->random->label; for (; pReScan != nullptr;) { if (pReScan->label == value) { pReCurr->random = pReScan; } pReScan = pReScan->next; } } pInCurr = pInCurr->next; pReCurr = pReCurr->next; } return pReHead; } };