经典链表拷贝算法

经典链表拷贝算法

问题描述：

• rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null,给定一个由Node节点组成的无环单链表的头节点head,实现链表的复制，并返回新链表的头节点。
• 时间复杂度O（N),额外空间复杂度O（1）

链表结构：

class Node {
public:
    Node* next=NULL;
    Node* rand=NULL;
    int value;
    Node(int _value) {
        this->value = _value;
    }
};

实现方式：
1、通过节点的拷贝形成新的链表
代码实现：

Node* cur = head;
    Node* next = NULL;
    //构建克隆指针
    while (cur != NULL) {
        next = cur->next;
        cur->next = new Node(cur->value);
        cur->next->next = next;
        cur = next;
    }

2、构建rand指针
代码实现：

 cur = head;
    Node* nodeCopy = NULL;
    while (cur != NULL) {
        next = cur->next->next;
        nodeCopy = cur->next;
        nodeCopy->rand = cur->rand != NULL ? cur->rand->next : NULL;
        cur = next;
    }

3、拆分链表
代码实现：

 Node* res = head->next;
    cur = head;
    while (cur != NULL) {
        next = cur->next->next;
        nodeCopy = cur->next;
        cur->next = next;
        nodeCopy->next = next != NULL ? next->next : NULL;
        cur = next;
    }

全部实现代码如下：

Node* CopyNode(Node* head) {
    if (head == NULL) {
        return NULL;
    }
  
    Node* cur = head;
    Node* next = NULL;
    //构建克隆指针
    while (cur != NULL) {
        next = cur->next;
        cur->next = new Node(cur->value);
        cur->next->next = next;
        cur = next;
    }
    printNode(head);

    //构建rand
    cur = head;
    Node* nodeCopy = NULL;
    while (cur != NULL) {
        next = cur->next->next;
        nodeCopy = cur->next;
        nodeCopy->rand = cur->rand != NULL ? cur->rand->next : NULL;
        cur = next;
    }
    std::cout << "rand" << std::endl;
    printNode1(head);
    printNode1(head->next);

    //拆分链表
    Node* res = head->next;
    cur = head;
    while (cur != NULL) {
        next = cur->next->next;
        nodeCopy = cur->next;
        cur->next = next;
        nodeCopy->next = next != NULL ? next->next : NULL;
        cur = next;
    }
    printNode(res);

    DeleteNode(cur);
    DeleteNode(next);

    return res;
}