【剑指Offer】复杂链表的复制
发布日期:2022-02-10 08:55:14 浏览次数:32 分类:技术文章

本文共 1512 字,大约阅读时间需要 5 分钟。

题目

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null。

思路

拿到题的思路就是hash表+两次遍历,但看到书上有更能节省空间的办法后就直接写了书上的。

翻了个错误就是奇偶链表节点的处理上,还是不能拿个整数做%2操作来判断,需要指针处理,因为最后一个空节点不复制。

总的来说就是三个方法顺序操作一下。

代码

/*// Definition for a Node.class Node {public:    int val;    Node* next;    Node* random;        Node(int _val) {        val = _val;        next = NULL;        random = NULL;    }};*/class Solution {public:    Node* copyRandomList(Node* head) {        if(head == NULL){            return NULL;        }        copyList(head);        changeptr(head);        return GetNewList(head);    }    void copyList(Node* head){        Node* p = head;        while(p != NULL){            Node* pclone = new Node(p->val);            Node* p1 = p->next;            p->next = pclone;            pclone->next = p1;            p=pclone->next;        }    }    void changeptr(Node* head){        Node* p = head;                while(p != NULL){            Node* pnew = p->next;            if(p->random != NULL){                pnew->random = p->random->next;            }            p=pnew->next;        }    }    Node* GetNewList(Node* head){        Node* p = head;        Node* pnewhead = NULL;        Node* pnew = NULL;        pnewhead = p->next;        pnew = p->next;        p->next = pnewhead->next;        p = p->next;        while(p != NULL){            pnew->next = p->next;            pnew = p->next;            p->next = pnew->next;            p=p->next;        }        return pnewhead;    }};

 

转载地址:https://blog.csdn.net/hanmin822/article/details/105699205 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【剑指Offer】二叉搜索树与双向链表
下一篇:【剑指Offer】顺时针打印矩阵

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年03月26日 06时21分22秒