前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Leetcode Copy List with Random Pointer(面试题推荐)

Leetcode Copy List with Random Pointer(面试题推荐)

作者头像
xindoo
发布2021-01-21 18:09:29
3140
发布2021-01-21 18:09:29
举报
文章被收录于专栏:XINDOO的专栏XINDOO的专栏

给大家推荐一道leetcode上的面试题,这道题的具体讲解在《剑指offer》的P149页有思路讲解,如果你手头有这本书,建议翻阅。

题目链接 here

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

RandomList中,每个节点不光有一个next指针,而且每个链表节点都有一个random指针,随机指向链表中的一个节点,让你复制这个链表,节点的C++定义如下。

代码语言:javascript
复制
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */

看到这个题目,估计很多人的第一反应是,先把这个单链表复制出来,然后挨个找random指向的节点。仔细想想这样效率很低,复制链表很快,但确定每个节点的random指针就不容易了,用这种方法的话,每找一个random指针,都必须遍历一次链表。时间复杂度O(n^2)。

可能也有人可能会想到时间换空间的方法,用hash把时间复杂度降到O(n)。

当然,还有更省时省空间的方法。

大概思路就是,在原链表的基础上,把每个节点复制一份加的原来节点的后面,然后设置好新节点random指针,在把所有的新节点从原链表中分离出来,构成一个新链表,这个链表就是我们要的原链表的拷贝。

下面有三个函数,第一个明显就是复制新节点并把其加入到被复制节点的后面。第二个,因为新节点的random指针还是指向旧节点的,要把它指向新节点,很简单,因为每个节点的新节点都是在原来的节点之后的。 第三个函数,把新节点从原链表中抽离,构成一个新链表。

这种方法的好处就是,时间复杂度只有O(n),而且我们不需要额外的空间。

代码语言:javascript
复制
class Solution {
public:
    void CloneNode(RandomListNode *head) {
        RandomListNode * p = head;
        while (NULL != p) {
            RandomListNode * CloneNode = new RandomListNode(p->label);
            CloneNode->next = p->next;
            CloneNode->random = p->random;
            p->next = CloneNode;
            p = CloneNode->next;
        }
    }
    
    void ConnectRandomNode(RandomListNode * head) {
        RandomListNode * p = head;
        while (NULL != p) {
            RandomListNode *pclone = p->next;
            if (NULL != pclone->random) {
                pclone->random = pclone->random->next;
            }
            p = pclone->next;
        }
    }
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (NULL == head)
            return head;
        CloneNode(head);
        ConnectRandomNode(head);
        RandomListNode *pnode = head;
        RandomListNode *pclonehead = pnode->next;
        RandomListNode *pclonenode = pnode->next;
        while (NULL != pnode) {
            pnode->next = pclonenode->next;
            pnode = pnode->next;
            if (NULL != pnode){
                 pclonenode->next = pnode->next;
                 pclonenode = pclonenode->next;
            }
        }
        return pclonehead;
    }
    
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2014-07-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档