剑指offer：复杂链表的复制

骑猪看日落 2022-08-05 08:54 145阅读 0赞

## 题目描述 ##

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。

#include <stdlib.h>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <queue>
    
    using namespace std;
    
    struct RandomListNode {
        int label;
        struct RandomListNode *next, *random;
        RandomListNode(int x) :
                label(x), next(NULL), random(NULL) {
        }
    };
    
    
    void printList(RandomListNode* pHead)
    {
    	while(pHead)
    	{
    		cout << pHead->label << " " ;
    		pHead = pHead->next;
    	}
    	cout << endl;
    }
    class Solution {
    public:
        RandomListNode* Clone(RandomListNode* pHead)
        {
    		if(NULL == pHead)
    		{
    			return NULL;
    		}
    
    		RandomListNode* pTempNode = NULL;
    		RandomListNode* pTempHead = pHead;
    		RandomListNode* pNewNode = NULL;
    		RandomListNode* pNewHead = NULL;
    
    		/* 复制一份，同时把两个链表接起来 */
    		while(pTempHead)
    		{
    			pNewNode = new RandomListNode(pTempHead->label);
    			
    			pTempNode = pTempHead;
    			pTempHead = pTempHead->next;
    
    			pTempNode->next = pNewNode;
    			pTempNode = pTempNode->next;
    			pTempNode->next = pTempHead;
    		}
    
    		/* 把random指针接起来 */
    		pTempHead = pHead;
    		while(pTempHead)
    		{
    			if(NULL != pTempHead->random)
    			{
    				pTempHead->next->random = pTempHead->random->next;
    			}
    			pTempHead = pTempHead->next->next;
    		}
    
    		/* 把链表拆分成两个单独的链表 */
    		pTempHead = pHead;
    		pNewHead = pTempHead->next;
    		pNewNode = pNewHead;
    		pTempHead = pTempHead->next->next;
    
    		RandomListNode* pTemp = pHead;
    		while(pTempHead)
    		{
    			pTempNode = pTempHead;
    			pTempHead = pTempHead->next->next;
    
    			pTemp->next = pTempNode;
    			pNewNode->next = pTempNode->next;
    		
    			pTemp = pTemp->next;
    			pNewNode = pNewNode->next;
    		}
    
    		/* 需要保证原来链表不变 */
    		pTemp->next = NULL;
    
    		return pNewHead;
        }
    };
    
    int main(void)
    {
    	int a[7] = {4,8,6,12,16,14,10};
    	vector<int> vec(a,a+7);
    	Solution s;
    
    	RandomListNode* phead = NULL;
    	RandomListNode* pNode = NULL;
    
    	phead = (RandomListNode*)malloc(sizeof(RandomListNode));
    	phead->label = 1;
    	phead->next = NULL;
    	phead->random  =NULL;
    
    	pNode = (RandomListNode*)malloc(sizeof(RandomListNode));
    	pNode->label = 2;
    	pNode->next = NULL;
    	pNode->random  =NULL;
    
    	phead->next = pNode;
    
    
    	RandomListNode* pTemp = phead;
    	while(pTemp)
    	{
    		cout << pTemp->label << " " ;
    		pTemp = pTemp->next;
    	}
    	cout << endl;
    
    	pTemp = s.Clone(phead);
    
    	while(pTemp)
    	{
    		cout << pTemp->label << " " ;
    		pTemp = pTemp->next;
    	}
    	cout << endl;
    
    	return 0;
    }