复制复杂链表

ryluo 2020-07-04 15:45:14

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

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

注意

分析:

  1. 链表的复制,指的是新链表中的所有元素的地址和之前的都不一样,也就是需要new出来一个新的

算法步骤:

  1. 遍历一遍,在每个节点后面接上该当前节点的复制节点
  2. 遍历一遍,判断原链表中的节点的random是否为空,如果不为空,那就把当前节点的复制节点的random指针赋值为当前节点的random节点的next节点
  3. 开辟一个虚拟头节点,遍历一遍链表,将两个链表分离开
image-20200704154525006
/**
 * 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 copy = new ListNode(p->val);
            auto next = p->next;
            p->next = copy;
            copy->next = next;
            p = next;
        }

        for(auto p = head; p;){
            if(p->random) 
                p->next->random = p->random->next;
            p = p->next->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;
    }
};