使用c++编写有一个带头结点的单链表L，每个结点值由单个数字、小写字母和大写字母构成。设计一个算法将其拆分成3个带头结点的单链表L1、L2和L3，L1包含L中的所有数字结点，L2包含L中的所有小写字母结点，L3包含L中的所有大写字母结点。

### 回答1：

可以使用以下算法来实现：1. 建立三个带头结点的单链表L1、L2和L3，分别用来存放数字结点、小写字母结点和大写字母结点。2. 定义三个指针分别指向L1、L2和L3的头结点，用来插入新的结点。3. 遍历原链表L，判断当前结点是数字、小写字母还是大写字母，并将其插入相应的单链表中。4. 遍历结束后，返回L1、L2和L3三个链表。

### 回答2：
算法如下：
1. 初始化L1、L2和L3的头结点；
2. 定义三个指针p1、p2和p3，分别指向L1、L2和L3的最后一个结点；
3. 从L的第一个结点开始遍历链表；
4. 如果当前结点的值是数字，则将该结点添加到L1的尾部，然后移动p1指针指向L1的最后一个结点；
5. 如果当前结点的值是小写字母，则将该结点添加到L2的尾部，然后移动p2指针指向L2的最后一个结点；
6. 如果当前结点的值是大写字母，则将该结点添加到L3的尾部，然后移动p3指针指向L3的最后一个结点；
7. 遍历完所有结点后，L1、L2和L3分别包含了L中的所有数字结点、小写字母结点和大写字母结点；
8. 将L1、L2和L3的最后一个结点的next指针指向NULL，表示链表结束；
9. 返回L1、L2和L3的头结点，即拆分后的三个链表。

该算法的时间复杂度为O(n)，其中n为L的结点数。使用三个指针p1、p2和p3记录每个链表的最后一个结点，可以在时间复杂度为O(1)的情况下将结点添加到链表的尾部。

### 回答3：
算法描述如下：
1. 创建3个带头结点的单链表L1、L2和L3，分别用于存储数字结点、小写字母结点和大写字母结点。
2. 遍历链表L中的每一个结点：
a. 如果当前结点是数字结点，则将其加入到L1链表中。
b. 如果当前结点是小写字母结点，则将其加入到L2链表中。
c. 如果当前结点是大写字母结点，则将其加入到L3链表中。
3. 遍历完链表L后，得到拆分后的三个链表L1、L2和L3。

代码实现如下：

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

// 定义链表结点
typedef struct Node {
    char value;
    struct Node* next;
} Node;

// 创建带头结点的单链表
Node* createList() {
    Node* head = (Node*) malloc(sizeof(Node));
    head->next = NULL;
    return head;
}

// 将结点加入到链表的尾部
void addNode(Node* list, char value) {
    Node* newNode = (Node*) malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = NULL;

    Node* cur = list;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

// 拆分链表
void splitList(Node* L, Node* L1, Node* L2, Node* L3) {
    Node* cur = L->next;
    while (cur != NULL) {
        if (cur->value >= '0' && cur->value <= '9') {
            addNode(L1, cur->value);
        } else if (cur->value >= 'a' && cur->value <= 'z') {
            addNode(L2, cur->value);
        } else if (cur->value >= 'A' && cur->value <= 'Z') {
            addNode(L3, cur->value);
        }
        cur = cur->next;
    }
}

// 打印链表
void printList(Node* list) {
    Node* cur = list->next;
    while (cur != NULL) {
        printf("%c ", cur->value);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    Node* L = createList();
    // 假设链表L中的结点值为：124abcXYZ
    addNode(L, '1');
    addNode(L, '2');
    addNode(L, '4');
    addNode(L, 'a');
    addNode(L, 'b');
    addNode(L, 'c');
    addNode(L, 'X');
    addNode(L, 'Y');
    addNode(L, 'Z');

    Node* L1 = createList();
    Node* L2 = createList();
    Node* L3 = createList();
    splitList(L, L1, L2, L3);

    printf("L1: ");
    printList(L1);

    printf("L2: ");
    printList(L2);

    printf("L3: ");
    printList(L3);

    return 0;
}

输出结果：

L1: 1 2 4
L2: a b c
L3: X Y Z

这样就将链表L按照数字、小写字母和大写字母进行了拆分。