leetcode刷题记录链表-01

原题链接

1. 题目描述

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

1.1 示例

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

其他示例见原题链接
1.2 提示

-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。

2. 解答

此题比较取巧的思路是，直接返回这个链表。但是现在LeetCode不会通过,hhhh....。我们的做法是把每一个节点进行复制，然后修改指向，最后把复制后的链表节点，通过一个节点串起来，最后返回这个复刻就行。

• 步骤如下：

• 复制所有节点

• 把random指针指向对应节点

• 用一个节点把复刻的节点串起来

• 代码：

  /* Definition for a Node.
  class Node {
  public:
    int val;
    Node* next;
    Node* random;
  
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
  };*/
  class Solution {
  public:
    Node* copyRandomList(Node* head) {
    // 所有节点的复制
    for(auto p = head;p;){
        auto np = new Node(p->val);
        auto next = p->next; // 复制一份
        p->next = np;    
        np->next = next; //连接起来
        p = next;  //遍历到下一个节点
    }
    // 让random指针指向对应的指针
    for(auto q = head; q; q = q->next->next){
        if(q->random)
            q->next->random = q->random->next;
        //else
           // q->next->random = q->random;
    }
    auto dummy = new Node(-1);
    auto cur = dummy;
    // 创建节点把后面复制的三个点串起来
    for(auto m = head; m ;m=m->next){
        cur->next = m->next; 
        cur = cur->next;
        m->next = m->next->next;
    }
    return dummy->next;
    }
  };