文档章节

复杂链表的复制

大大美女女
 大大美女女
发布于 2013/12/10 15:22
字数 285
阅读 140
收藏 8

 题目:有一个复杂链表,其结点除了有一个 m_pNext 指针指向下一个结点外,还有一个 m_pSibling 指向链表中的任一结点或者 NULL 。其结点的 C++ 定义如下:

                struct ComplexNode

{

    int m_nValue;

    ComplexNode* m_pNext;

    ComplexNode* m_pSibling;

};

                下图是一个含有5个结点的该类型复杂链表。图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,指向NULL的指针没有画出。

 

                  程序员面试题精选100题(49)-复杂链表的复制 - 何海涛 - 微软、Google等面试题  

                

请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。

 

 

struct ComplexNode {
  ComplexNode* next;
  ComplexNode* random;
  int value;
};

void CloneNext(ComplexNode* origin) {
  if (NULL == origin) {
    return;
  }
  ComplexNode* current = origin;
  while (current) {
    ComplexNode* temp = new ComplexNode();
    temp->value = current->value;
    temp->random = NULL:
    temp->next = current->next;
    current->next = temp;
    current = temp->next;
  }
}

void CloneRandom(ComplexNode* origin) {
  if (NULL == origin) {
    return;
  }
  ComplexNode* current = origin;
  ComplexNode* clone = NULL;

  while (current) {
    clone = current->next;
    if (current->random) {
      clone->random = current->random->next;
    }
    current = clone->next;
  }

}


ComplexNode* Clone(ComplexNode* origin) {
  ComplexNode* clone_head = NULL;    
  ComplexNode* clone_node = NULL;    
  ComplexNode* node = origin;    
  if (node) {
    clone_head = node->next;
    clone_node = node->next;
  }
  while (node) {
    node->next = clone_node->next;
    node = node->next;
    clone_node->next = node->next;
    clone_node = clone_node->next;
    
  }
  return clone_head;
}



int main(int argc, char* argv[]) {

}


这个实现没有考虑链表中有环的情况

 

 

 

 

有趣有爱有价值:http://www.qihu100.com

 

© 著作权归作者所有

共有 人打赏支持
大大美女女
粉丝 18
博文 60
码字总数 24479
作品 0
昌平
程序员
复杂链表的复制

题目:复制一个复杂链表。在复杂链表中,每个结点除了有一个next指针指向下一个结点外,还有一个sibling指向链表中的任意结点或者null。 解题思路:第一步,根据原始链表的每个结点N创建对应...

许大树
2017/10/26
0
0
单链表复制你已经会了,如果我们再加个指针...

面试 18:复杂链表的复制(剑指 Offer 第 26 题) 在上一篇推文中,我们留下的习题是来自《剑指 Offer》 的面试题 26:复杂链表的复制。 请实现复杂链表的复制,在复杂链表中,每个结点除了 ...

nanchen2251
08/01
0
0
单链表复制早已难不到你,但若我们再加个指针...

面试 18:复杂链表的复制(剑指 Offer 第 26 题) 在上一篇推文中,我们留下的习题是来自《剑指 Offer》 的面试题 26:复杂链表的复制。 请实现复杂链表的复制,在复杂链表中,每个结点除了 ...

南尘
08/01
0
0
面试 18:复杂链表的复制(剑指 Offer 第 26 题)

面试 18:复杂链表的复制(剑指 Offer 第 26 题) 在上一篇推文中,我们留下的习题是来自《剑指 Offer》 的面试题 26:复杂链表的复制。 请实现复杂链表的复制,在复杂链表中,每个结点除了 ...

nanchen2251
08/01
0
0
经典单链表练习题(2)

问题: 删除链表的倒数第K个结点 判断单链表是否带环?若带环,求环的长度?求环的入口点?并计算每个算法的时间复杂度&空间复杂度。 判断两个链表是否相交,若相交,求交点。(假设链表不带...

triorwy
01/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

腾讯投资最高1.75亿美元正式进军菲律宾移动支付市场

菲律宾长途电话公司(PLDT)公司今日宣布,中国互联网巨头腾讯和私募股权公司KKR将获得该公司旗下金融科技公司Voyager Innovations的少数股权。 PLDT在一份声明中称:“腾讯和KKR最多将分别收...

linuxCool
17分钟前
1
0
正则介绍及grep/egrep用法

10月16日任务 9.1 正则介绍_grep上 9.2 grep中 9.3 grep下 扩展 把一个目录下,过滤所有*.php文档中含有eval的行 grep -r --include="*.php" 'eval' /data 正则介绍 正则就是一串有规律的字符...

hhpuppy
28分钟前
0
0
J2Cache 中使用 Lettuce 替代 Jedis 管理 Redis 连接

一直以来 J2Cache 都是使用 Jedis 连接 Redis 服务的。Jedis 是一个很老牌的 Redis 的 Java 开发包,使用很稳定,作者维护很勤勉,社区上能搜到的文章也非常非常多。算是使用范围最广的 Redi...

红薯
今天
11
0
一个可能的NEO链上安全随机数解决方案

0x00 困境 链上安全随机数生成应该算是一个比较蛋疼的问题,哪怕你的系统再牛逼,合约程序困在小小的虚拟机里,哪怕天大的本事也施展不开。 更悲催的是,交易执行的时候,是在每一个节点都执...

暖冰
今天
1
0
【大福利】极客时间专栏返现二维码大汇总

我已经购买了如下专栏,大家通过我的二维码你可以获得一定额度的返现! 然后,再给大家来个福利,只要你通过我的二维码购买,并且关注了【飞鱼说编程】公众号,可以加我微信或者私聊我,我再...

飞鱼说编程
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部