创建一个带头结点的单链表

好的，下面是代码示例：

typedef struct Node {
    int val;
    struct Node* next;
} Node;

Node* createLinkedList(int* arr, int n) {
    Node* head = (Node*) malloc(sizeof(Node));
    head->val = -1; // 头结点不存储有效值
    head->next = NULL;
    Node* cur = head;
    for (int i = 0; i < n; i++) {
        Node* node = (Node*) malloc(sizeof(Node));
        node->val = arr[i];
        node->next = NULL;
        cur->next = node;
        cur = cur->next;
    }
    return head;
}

这段代码可以创建一个带头结点的单链表，并将传入的数组元素加入到链表中。

相关问题

创建一个带头结点单链表

创建一个带头结点的单链表通常涉及以下几个步骤：

1. **定义结构**：
首先，我们需要定义一个链表节点的数据结构，包含两个部分：数据域 `data` 和指针域 `next`。在带头结点的情况下，头结点通常是特殊的，它的 `data` 可能为空或者用于存储特定的信息。

typedef struct ListNode {
    int data;        // 节点存储的数据
    struct ListNode* next; // 指向下一个节点的指针
} ListNode;

2. **创建头结点**：
初始化一个头结点，可以设置其 `next` 指针指向自身，表示链表开始于头结点。

ListNode* head = (ListNode*)malloc(sizeof(ListNode));
head->data = 0;      // 或者设置特定值
head->next = head;

3. **添加元素**：
向链表中添加新节点需要创建一个新的节点，并将其 `next` 指针连接到当前节点的 `next` 指针上。

void insertNode(ListNode* &head, int value) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = value;
    newNode->next = head->next;
    head->next = newNode;
}

4. **遍历链表**：
如果需要访问链表的所有元素，可以从头结点开始通过 `next` 指针逐个遍历。

void printList(ListNode* head) {
    ListNode* current = head->next;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

设有带头结点单链表A和B，其结点均已按值升序排列，编写一个算法将他们合并成一个按值升序排列的带头结点单链表。

要合并两个已按值升序排列的带头结点单链表A和B，可以创建一个新的链表，并通过迭代或递归的方式将它们连接起来。这里提供一种简单的迭代方法：

1. 创建新链表C，初始化为一个空头结点。
2. 定义两个指针，分别指向A和B的头结点。
3. 比较两个当前指针所指节点的值：
- 如果A的值小于或等于B的值，将A的下一个节点添加到新链表C中，然后移动A指针。
- 否则，将B的下一个节点添加到新链表C中，然后移动B指针。
4. 当其中一个链表遍历完（即为空），将另一个链表剩余的部分直接添加到新链表的末尾。
5. 新链表C的头结点就是最终合并后的有序链表。

下面是伪代码描述：

def merge_sorted_lists(headA, headB):
    if not headA: return headB
    if not headB: return headA

    dummy = ListNode(0)  # 创建虚拟头结点
    tail = dummy

    while headA and headB:
        if headA.val <= headB.val:
            tail.next = headA
            headA = headA.next
        else:
            tail.next = headB
            headB = headB.next
        tail = tail.next

    # 将剩余的链表添加到新链表末尾
    if headA:
        tail.next = headA
    elif headB:
        tail.next = headB

    return dummy.next