C语言复杂链表的复制实例详解

非常感谢您对C语言复杂链表复制实例的关注。本篇攻略将为您详细介绍该算法的实现过程和运行示例。

什么是复杂链表

在介绍复杂链表的复制算法之前，我们先了解一下什么是复杂链表。

复杂链表是在单向链表的基础上增加了random指针，该指针指向链表中的任意节点（包括自身和NULL），这意味着链表中可能存在环。

复杂链表复制实例详解

算法思路

复杂链表的复制算法可以分为以下三个步骤：

1. 遍历原链表，复制每个节点，并将新节点插入到原节点的后面；
2. 遍历复制后的链表，根据每个节点的random指针，设置新节点的random指针；
3. 将复制后的链表与原链表分离，得到新的复杂链表。

代码实现

下面是C语言中复杂链表的复制实现代码：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node* next;
 *     struct Node* random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) return NULL;

    // 第一步：复制每个节点，将新节点插入到原节点的后面
    struct Node* cur = head;
    while (cur != NULL) {
        struct Node* tmp = cur->next;
        cur->next = (struct Node*)malloc(sizeof(struct Node));
        cur->next->val = cur->val;
        cur->next->next = tmp;
        cur = tmp;
    }

    // 第二步：设置新节点的random指针
    cur = head;
    while (cur != NULL) {
        if (cur->random != NULL)
            cur->next->random = cur->random->next;
        cur = cur->next->next;
    }

    // 第三步：将复制后的链表与原链表分离
    cur = head;
    struct Node* newHead = head->next;
    while (cur != NULL) {
        struct Node* tmp = cur->next;
        cur->next = tmp->next;
        if (tmp->next != NULL)
            tmp->next = tmp->next->next;
        cur = cur->next;
    }

    return newHead;
}

示例说明

假设我们有以下一个复杂链表：

原链表

   ------   random: ------> D
  |        val: A
  V
  A ------> B ------> C ------> D
         random: ------> B

1. 第一步：复制每个节点，将新节点插入到原节点的后面。

  A ------> A' ------> B ------> B' ------> C ------> C' ------> D ------> D'
         random:  ^        random:  ^        random:  ^        random:  ^
                   |                  |                  |                  |
                   ------------------                  ------------------

1. 第二步：设置新节点的random指针。

  A ------> A' ------> B ------> B' ------> C ------> C' ------> D ------> D'
         random:  ^         random: ^         random:  ^        random:  ^
                   |                   |                   |                  |
                   -------> D         -------> B        -------> D      -------> C'

1. 第三步：将复制后的链表与原链表分离。

   ------   random: ------> D
  |        val: A
  V
  A ------> B ------> C ------> D
         random: ------> B

   ------   random: ------> D
  |        val: A
  V
  A'------> B'------> C'------> D'
         random: ------> B'

经过三个步骤的处理，我们得到了从原链表复制而来的新链表。

示例二

再来看一个示例：

原链表

   ------   random: ------>
  |        val: A
  V
  A ------> NULL
         random: ------> A

1. 第一步：复制每个节点，将新节点插入到原节点的后面。

  A ------> A' ------> NULL
         random:  ^        random:  ^
                   |                  |
                   ------------------                  

1. 第二步：设置新节点的random指针。

  A ------> A' ------> NULL
         random:  ^         random: ^   
                   |                   |
                   -------> A      -------> A'

1. 第三步：将复制后的链表与原链表分离。

   ------   random: ------>
  |        val: A
  V
  A ------> NULL
         random: ------> A

   ------   random: ------>
  |        val: A
  V
  A'------> NULL
         random: ------> A'

接下来，您可以结合代码和示例，在自己的C语言程序中使用该复制算法，实现复杂链表的复制。