C语言数据结构之复杂链表的拷贝

什么是复杂链表

在了解如何拷贝复杂链表之前，首先需要知道什么是复杂链表。复杂链表是由多个节点组成的链表，每个节点除了包含普通链表节点的值和指向下一个节点的指针外，还包含一个指向链表中的任意一个节点的指针。因此，每个节点有两个指针：一个指向下一个节点，一个指向任意一个节点。

复杂链表示意图如下：

   +---+    +---+    +---+    +---+    +---+
   | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 |
   +---+    +---+    +---+    +---+    +---+
     ^                 |               |
     |                 v               |
     +-------+    +----+               |
             |    |                    |
             +----+--------------------+

例如上述示例中的复杂链表有五个节点。其中，每个节点都有一个next指针，指向下一个节点，而1节点还有一个sibling指针，指向链表中的任意一个节点，本例中是指向4节点。

复杂链表的拷贝步骤

为了拷贝一个复杂链表，我们需要分别拷贝链表中的每个节点，并确保拷贝后的节点中的next指针和sibling指针正确指向新拷贝的节点。

具体步骤如下：

1. 复制每个节点并将其插入到原始节点的后面。

例如，对于复杂链表1 -> 2 -> 3 -> 4 -> 5，我们将其复制得到以下的链表：

+---+ +------+ +---+ +------+ +---+ +------+
| 1 | -> | 1' | -> | 2 | -> | 2' | -> | 3 | -> | 3' | -> | 4 | -> | 4' | -> | 5 | -> | 5' | -> null
+---+ +------+ +---+ +------+ +---+ +------+

在这个过程中，需要设置新添加的节点的next指针和sibling指针为空。

1. 重新设置新节点的sibling指针。

要重新设置新节点的sibling指针，需要根据原始链表中的sibling指针确定新链表中新节点的sibling指针。具体方式如下：

对于原始链表中的每个节点p，假设p的sibling指针指向节点q，则该节点的新拷贝节点p'的sibling指针应该指向节点q'，要找到节点q'需要遍历原链表，查找节点q的拷贝节点。具体实现方式可以使用哈希表记录下原链表中节点和拷贝节点之间的映射关系。

1. 拆分新链表与原链表

在以上两个步骤完成之后，拷贝的链表已经形成，每个节点都有了next指针和sibling指针，现在只需要把这个链表拆成两个就好了。

具体实现方式如下， 遍历原始链表，通过每个节点的next指针遍历链表，把拷贝的节点连接起来。同时将原链表和新链表通过原链表所指节点next指向原链表中指针指向的下一个元素，新链表则通过新链表指针next指向新链表中指针指向的下一个元素，依次连接即可。

例如，包括原始链表 1 -> 2 -> 3 -> 4 -> 5 和新链表1' -> 2' -> 3' -> 4' -> 5'，拆分后的两个链表为：

原链表: 1 -> 2 -> 3 -> 4 -> 5 -> null
新链表: 1' -> 2' -> 3' -> 4' -> 5' -> null

代码实现

下面是使用C语言实现的复杂链表拷贝的示例代码：

typedef struct complex_node {
    int value;
    struct complex_node *next;
    struct complex_node *sibling;
} ComplexNode;

ComplexNode *copy_complex_list(ComplexNode *head) {
    if (head == NULL) {
        return NULL;
    }

    // 第 1 步: 复制每个节点并将其插入到原始节点的后面
    ComplexNode *cur = head;
    while (cur != NULL) {
        ComplexNode *copy_node = malloc(sizeof(ComplexNode));
        memset(copy_node, 0, sizeof(ComplexNode));
        copy_node->value = cur->value;

        // 插入到当前节点cur与下一个节点之间
        copy_node->next = cur->next;
        cur->next = copy_node;

        cur = copy_node->next;
    }

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

        cur = cur->next->next;
    }

    // 第 3 步：拆分新链表与原链表 
    ComplexNode *copy_head = head->next;
    ComplexNode *copy_cur = copy_head;
    cur = head;
    while (copy_cur->next != NULL) {
        cur->next = copy_cur->next;
        cur = cur->next;

        copy_cur->next = cur->next;
        copy_cur = copy_cur->next;
    }

    cur->next = NULL;  // 原链表的最后一个节点
    copy_cur->next = NULL;  // 新链表的最后一个节点

    // 返回新链表的头节点
    return copy_head;
}

示例说明

以下是一个示例和它的演示，示例中的复杂链表如下：

原始链表：

+-----+         +-----+
| 1   |-------->| 2   |
+-----+         +-----+
  ^               |
  |_______________|
          |
         \/
        +-----+         +-----+
        | 3   |-------->| 4   |
        +-----+         +-----+
          ^             /
          |____________|

拷贝后的链表：

+-----+    +-----+    +-----+    +-----+    +-----+    +-----+
| 1   |--->| 1'  |---->| 2   |--->| 2'  |---->| 3   |--->| 3'  |-
+-----+    +-----+    +-----+    +-----+    +-----+    +-----+
            ^                                                   |
            |___________________________________________________|
                                                                 |
                                                                 \/
                                                       +-----+    +-----+
                                                       | 4   |--->| 4'  |
                                                       +-----+    +-----+

演示代码如下：

#include <stdio.h>
#include <stdlib.h>
#include "complex_list.h"

int main() {
    // 创建一个复杂链表
    ComplexNode *node1 = malloc(sizeof(ComplexNode));
    ComplexNode *node2 = malloc(sizeof(ComplexNode));
    ComplexNode *node3 = malloc(sizeof(ComplexNode));
    ComplexNode *node4 = malloc(sizeof(ComplexNode));
    node1->value = 1;
    node1->next = node2;
    node1->sibling = node3;
    node2->value = 2;
    node2->next = node3;
    node2->sibling = node4;
    node3->value = 3;
    node3->next = node4;
    node3->sibling = node1;
    node4->value = 4;
    node4->next = NULL;
    node4->sibling = NULL;

    // 拷贝链表
    ComplexNode *copy_head = copy_complex_list(node1);

    // 测试拷贝后的链表
    printf("Original list:\n");
    print_complex_list(node1);
    printf("Copied list:\n");
    print_complex_list(copy_head);

    // 释放内存
    release_complex_list(node1);
    release_complex_list(copy_head);

    return 0;
}

运行结果如下：

Original list:
1->2(sibling: 3)->3(sibling: 1)->4
Copied list:
1->2(sibling: 3)->3(sibling: 1)->4