《剑指offer刷题笔记》36、复杂链表的复刻【c++详细题解】

分手后的思念是犯贱 2021-07-25 02:15 333阅读 0赞

### **题目** ###

请实现一个函数可以复制一个复杂链表。

在复杂链表中，每个结点除了有一个指针指向下一个结点外，还有一个额外的指针指向链表中的任意结点或者null。

**注意**：

*  函数结束后原链表要与输入时保持一致。

### **思路** ###

**原链表图形：** 虚线为`random`指针  
![20210413221436905.png][]

1、在每个节点的后面加上它的复刻，将原链表和复刻链表连在一起。  
![20210413221704352.png][]

2、从前往后遍历每一个原链表节点，对于有`random`指针的节点`p`，我们让它的`p->next->random = p->random->next`,这样我们就完成了对原链表`random`指针的复刻。  
![20210413221813445.png][]

3、最后我们把原链表和复刻链表拆分出来，并将原链表复原。  
![20210413221909301.png][]

### **代码** ###

/** * Definition for singly-linked list with a random pointer. * struct ListNode { * int val; * ListNode *next, *random; * ListNode(int x) : val(x), next(NULL), random(NULL) {} * }; */
    class Solution { 
    public:
        ListNode *copyRandomList(ListNode *head) { 
            for(auto p = head; p ; ) //遍历原链表
            {  
                auto np = new ListNode(p->val); //复刻节点
                auto next = p->next; //留存原链表当前节点p的下一个节点
                p->next = np;//将原链表当前节点p指向复刻节点
                np->next = next;//复刻节点np指向原链表当前节点的下一个节点
                p = next; //p指针后移
            }
            for (auto p = head; p; p = p->next->next)//对原链表random指针的复刻。
            { 
                if (p->random)
                    p->next->random = p->random->next;
            }
            auto dummy = new ListNode(-1); //虚拟头结点
            auto cur = dummy; //尾节点
            for (auto p = head; p; p = p->next) //将原链表和复刻链表拆分出来，并将原链表复原。
            { 
                cur->next = p->next;
                cur = cur->next;
                p->next = p->next->next;
            }
            return dummy->next;
        }
    };

[20210413221436905.png]: /images/20210724/1cb8f6ce60754a04aa17794da1b29efa.png
[20210413221704352.png]: /images/20210724/cd78a67bad6e4532b2ad14ad90efeaf6.png
[20210413221813445.png]: /images/20210724/e14cd25173864e6c88f6ca2a8a9775fb.png
[20210413221909301.png]: /images/20210724/f2402e0a8de84ad3af564af9016a9b9c.png