Copy List with Random Pointer

这题这种解法值得细品,想出来的人真的沾点天才了。。。我自己的笨方法还跑不通,接来下还得去调调看。

废话不多说,直接上代码。

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node * node = head;
        //第一个循环:将原链表进行复制,复制完后形如A->A'->B->B'->C->C'->NULL
        while(node){
            Node* temp = node->next;
            node->next = new Node(node->val);
            node->next->next = temp;
            node = temp;
        }
        node = head;
        //第二个循环:复制原链表的random指针
        while(node){
            if (node->random)
                node->next->random = node->random->next;
            node = node->next->next;
        }
        node = head;
        Node* ans = new Node(0);
        Node* helper = ans;
        //第三个循环:利用一个新建的哑结点将复制完后的新链表分出来
        while(node){
            helper->next = node->next;
            helper = helper->next;
            node->next = node->next->next;
            node = node->next;
        }
        return ans->next;
    }
};

emm等下看能不能把自己最原始的代码调通,可以的话也一起贴上来,看看彼此的差距(泪目)。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容