Ex35 复杂链表的复制

题目描述

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

解题思路

• 先在原地复制链表，原链表1->2->3->4->5，变成1->1->2->2->3->3->->4->4->5->5。只有next指针的改变。
• 复制链表的random指针，指向复制后的结点。
• 拆分两个链表。

代码

class Solution
{
public:
  Node *
  copyRandomList (Node *head)
  {
    if (!head)
      return head;
    Node *ptr = head;
    while (ptr)
      {
        Node *copy = new Node (ptr->val);
        copy->next = ptr->next;
        ptr->next = copy;
        ptr = ptr->next->next;
      }
    ptr = head;
    while (ptr)
      {
        if (ptr->random)
          {
            ptr->next->random = ptr->random->next;
          }
        ptr = ptr->next->next;
      }
    ptr = head->next;
    Node *pre = head, *res = head->next;
    while (ptr->next)
      {
        pre->next = pre->next->next;
        ptr->next = ptr->next->next;
        pre = pre->next;
        ptr = ptr->next;
      }
    pre->next = NULL;
    return res;
  }
};

结果

执行结果：通过

执行用时：16 ms, 在所有 C++ 提交中击败了82.38%的用户

内存消耗：11.3 MB, 在所有 C++ 提交中击败了22.82%的用户