C语言 — 链表面试题复杂链表问题

太过爱你忘了你带给我的痛 2022-09-30 12:58 157阅读 0赞

# 复杂链表 #

何为复杂链表呢？ 这个问题是我在一道面试题上看到的，觉得挺难理解的，所以写一篇博客 介绍一下

![Center][]

链表本身具有两个或多个指针，当然next指针很有规律的指向下一个结点，但是其他的指针的指向， 就有一点混乱了，可以说是没有规律

，现在问 题来 了，你需要复制一个这样的链表，怎么办？ 讲道理这些题是真的烧脑，首先我们普通的复制一个链表，肯定就是从头到尾遍

历一遍，但是这样 由于 你的random 指针毫无 规律，你不能一个一个的开 辟，所以这种开辟内存的方式是错误的。 我们不妨考虑一下别的方

法，来看看下面这种实现方 式：

![Center 1][]

现在链表已经链接起来，我们接下来看random指针如何解决：

![Center 2][]

接下来最后一步：

![Center 3][]

这个是问题的实现代码：

pcomplexNode clonelist(pcomplexNode list)
    {
    	pcomplexNode cur = list;
    	pcomplexNode prev = NULL;
    	pcomplexNode  l1= list;
    	pcomplexNode  l2= NULL;
    	while (cur)
    	{
    		prev = buylist2(cur->data);
    		prev->next = cur->next;
    		cur->next = prev;
    		cur = cur->next->next;
    	}
    	cur = list;
    
    	while (cur)
    	{
    		cur->next->random = cur->random->next;
    		cur = cur->next;
    	}
    
    	if (l1->next)
    	{
    		l2 = l1->next;
    	}
    	cur = l2;
    
    	while (l2->next)
    	{
    		l1->next = l2->next;
    		l1 = l1->next;
    		l2->next = l1->next;
    		l2 = l2->next;
    	}
    	l1->next = NULL;
    	
    	return cur;
    }

不过呢还有更骚的方法，让我大吃一惊！！！ 就是传说中的hash映射发！ 这里用到了map！！！ 让我们一起来看代码！ 这方法是

真的骚！！

struct ComplexListNode{
        int val;
        ComplexListNode* pNext;
        ComplexListNode* pSibling;
        ComplexListNode():val(0),pNext(NULL),pSibling(NULL){};
    };
     
    typedef std::map<ComplexListNode*,ComplexListNode*> MAP;
     
    ComplexListNode* CloneNodes(ComplexListNode* pHead,MAP &hashNode){
        ComplexListNode* pNode=new ComplexListNode();
        ComplexListNode* p=pNode;
        ComplexListNode* tmp;
     
        while(pHead!=NULL){
            tmp=new ComplexListNode();
            tmp->val=pHead->val;
            p->pNext=tmp;
            hashNode[pHead]=tmp;
            pHead=pHead->pNext;
            p=p->pNext;
        }
        return pNode->pNext;
    }
     
    void SetSiblings(ComplexListNode* pHead,ComplexListNode* pCopy,MAP &hashNode){
        while(pCopy!=NULL){
            pCopy->pSibling=hashNode[pHead->pSibling];
            pCopy=pCopy->pNext;
            pHead=pHead->pNext;
        }
    }
     
    ComplexListNode* ComplexListCopy(ComplexListNode* pHead){
        ComplexListNode* pCopy;
        MAP hashNode;
        pCopy=CloneNodes(pHead,hashNode);
        SetSiblings(pHead,pCopy,hashNode);
        return pCopy;
    }

[Center]: /images/20220705/4f740d39bf0f44eaaa4994a167233aea.png
[Center 1]: /images/20220705/e7f76a730b934a22aa15a2587e2fe17b.png
[Center 2]: /images/20220705/d8f1d99de57f4eec9e4b7f98fa8f1555.png
[Center 3]: /images/20220705/a37f8e54f26d4366bcc1550513b2c04c.png