复杂链表的复制
复杂链表的复制
大大美女女 发表于4年前
复杂链表的复制
  • 发表于 4年前
  • 阅读 136
  • 收藏 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
×
大大美女女
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: