/
* Definition for singly-linked list with a random pointer.
* struct ListNode {
* int val;
* struct ListNode next;
* struct ListNode random;
* };
*/

include [HTML_REMOVED]

typedef struct ListNode ListNode;

// 辅助函数：创建一个新节点
ListNode createNode(int val) {
ListNode node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
node->random = NULL;
return node;
}

// 主函数：复制带随机指针的链表
ListNode copyRandomList(ListNode head) {
if (!head) return NULL;

// 第一步：在原链表中插入复制节点
ListNode* p = head;
while (p) {
    ListNode* newNode = createNode(p->val);
    newNode->next = p->next;
    p->next = newNode;
    p = newNode->next;
}

// 第二步：复制 random 指针
p = head;
while (p) {
    if (p->random) {
        p->next->random = p->random->next;
    }
    p = p->next->next;
}

// 第三步：拆分原链表和复制链表
ListNode* dummy = createNode(-1);
ListNode* cur = dummy;
p = head;

while (p) {
    cur->next = p->next;
    cur = cur->next;
    p->next = p->next->next;
    p = p->next;
}

ListNode* copiedList = dummy->next;
free(dummy); // 释放虚拟头结点
return copiedList;

}