文档章节

复杂链表的复制

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

 题目:有一个复杂链表,其结点除了有一个 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

经典单链表练习题(2)

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

triorwy ⋅ 01/24 ⋅ 0

复杂单向链表的复制

一个单向的复杂链表,每个节点有两个指针,一个是next,一个是any指针。next指针指向下一个节点,any指针可以指向任意一个节点包括NULL。 把这个链表复制一遍,要求任意指针指向复制链表相对...

栗先生 ⋅ 2017/04/25 ⋅ 0

SkipList的那点事儿

Skip List的工作原理 Skip List(跳跃表)是一种支持快速查找的数据结构,插入、查找和删除操作都仅仅只需要对数级别的时间复杂度,它的效率甚至可以与红黑树等二叉平衡树相提并论,而且实现...

SylvanasSun ⋅ 2017/12/31 ⋅ 0

编程题——21~30

二十一、包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调 用min、push及pop的时间复杂度都是O(1)。 二十二、栈的压入、弹出序列 输入两...

thanatos_y ⋅ 2016/07/22 ⋅ 0

python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905 ⋅ 06/03 ⋅ 0

【死磕Java并发】—–J.U.C之Java并发容器:ConcurrentHashMap

此篇博客所有源码均来自JDK 1.8 HashMap是我们用得非常频繁的一个集合,但是由于它是非线程安全的,在多线程环境下,put操作是有可能产生死循环的,导致CPU利用率接近100%。为了解决该问题,...

chenssy ⋅ 2017/06/20 ⋅ 0

【死磕Java并发】-----J.U.C之Java并发容器:ConcurrentHashMap

此篇博客所有源码均来自JDK 1.8 HashMap是我们用得非常频繁的一个集合,但是由于它是非线程安全的,在多线程环境下,put操作是有可能产生死循环的,导致CPU利用率接近100%。为了解决该问题,...

chenssy ⋅ 2017/06/20 ⋅ 0

拷贝有随机指针的单链表

原题   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.......

一贱书生 ⋅ 2016/12/23 ⋅ 0

Redis源码分析(adlist)

源码版本: 源码位置: adlist.h : 数据结构定义。 adlist.c:函数功能实现。 一、adlist简介 Redis中的链表叫(A generic doubly linked list implementation 一个通用的双端链表实现),和普...

yangbodong22011 ⋅ 2017/11/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从方法论到零售客户实践 解码阿里巴巴数据中台——2018上海云栖大会

摘要: 一、数据中台之道 6月8日,上海云栖大会进入了第二天的议程,数据中台专场论坛座无虚席,数据中台总架构师邓中华女士向在场的观众介绍了数据中台的衍生发展之道。 基于OneID、OneData...

阿里云云栖社区 ⋅ 19分钟前 ⋅ 0

Ubuntu部署django问题汇总

使用Anaconda3的Python3.6的pip安装UWSGI报错 原因是gcc版本不兼容,安装4.7并修改gccsudo apt-get install gcc-4.7sudo mv /usr/bin/gcc /usr/bin/gcc.baksudo ln -s /usr/bin/gcc-4.......

wuyaSama ⋅ 22分钟前 ⋅ 0

从方法论到零售客户实践 解码阿里巴巴数据中台——2018上海云栖大会

摘要: 一、数据中台之道 6月8日,上海云栖大会进入了第二天的议程,数据中台专场论坛座无虚席,数据中台总架构师邓中华女士向在场的观众介绍了数据中台的衍生发展之道。 基于OneID、OneData...

猫耳m ⋅ 22分钟前 ⋅ 0

Docker减肥小记

如果经常使用 docker,你会发现 docker 占用的资源膨胀很快,其中最明显也最容易被察 如何快速的清理 docker 占用的系统资源,具体点说就是删除那些无用的镜像、容器、网络和数据卷… 1、查看...

寰宇01 ⋅ 33分钟前 ⋅ 0

微信小程序中如何使用WebSocket实现长连接(含完整源码)

本文由腾讯云技术团队原创,感谢作者的分享。 1、前言 微信小程序提供了一套在微信上运行小程序的解决方案,有比较完整的框架、组件以及 API,在这个平台上面的想象空间很大。腾讯云研究了一...

JackJiang- ⋅ 41分钟前 ⋅ 0

定制库到Maven本地资源库

1.如果只有定制库的JAR文件 下载链接如下:pdf.jar 2.使用命令转换成Maven本地资源 mvn install:install-file -Dfile=/Users/manager/Downloads/clj-pdf-2.2.33.jar -DgroupId=clj-pdf -Dar......

年少爱追梦 ⋅ 45分钟前 ⋅ 0

高仿springmvc之xuchen-mvc

package org.mvc.framework.servlet; import java.io.BufferedReader; import java.io.ByteArrayInputStream; import java.io.ByteArrayOutputStream; import java.io.File; import java.io.......

徐志 ⋅ 47分钟前 ⋅ 0

关于自定义URLStreamHandler的一次踩坑

关于自定义URLStreamHandler的一次踩坑 20180625 lambo init 说明 一般自定义实现url的协议解析.方案为实现URLStreamHandler.实现其 openConnection 就可以了, 如果我们执行 new URL("xx://...

林小宝 ⋅ 48分钟前 ⋅ 0

【SM2证书】利用BC的X509v3CertificateBuilder组装X509国密证书

演示证书文件 链接: https://pan.baidu.com/s/1ijHNnMQJj7jzW-jXEVd6Gg 密码: vfva 所需jar包 <!-- https://mvnrepository.com/artifact/org.bouncycastle/bcpkix-jdk15on --> <dependenc......

小帅帅丶 ⋅ 49分钟前 ⋅ 0

用Calendar 实现 计算 一段时间的毫秒值

Calendar c=Calendar.getInstance();c.add(Calendar.MONTH, -1);int lastMonthMaxDay=c.getActualMaximum(Calendar.DAY_OF_MONTH);c.set(c.get(Calendar.YEAR), c.get(Calendar.MONTH)......

岸芷汀兰 ⋅ 53分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部