两个有序链表序列的交集 C语言 带详细注释

以下是C语言的代码实现，带有详细注释：

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

struct ListNode {
    int val; // 存储节点的值
    struct ListNode *next; // 指向下一个节点的指针
};

typedef struct ListNode ListNode; // 定义一个简洁的类型别名

/**
 * @brief 获取两个有序链表的交集
 * @param head1 第一个链表的头节点
 * @param head2 第二个链表的头节点
 * @return 返回交集的新链表的头节点
 */
struct ListNode *getIntersectionNode(struct ListNode *head1, struct ListNode *head2) {
    ListNode* p1 = head1; // 指向第一个链表的指针
    ListNode* p2 = head2; // 指向第二个链表的指针
    ListNode* head = (ListNode*)malloc(sizeof(ListNode)); // 创建一个虚拟头节点
    ListNode* tail = head; // tail指向新链表的尾节点

    // 只要两个链表都还有节点，就继续遍历
    while (p1 && p2) {
        // 如果第一个链表的当前节点的值比第二个链表的当前节点的值小
        if (p1->val < p2->val) {
            p1 = p1->next; // 将第一个链表的指针向后移动一位
        }
        // 如果第一个链表的当前节点的值比第二个链表的当前节点的值大
        else if (p1->val > p2->val) {
            p2 = p2->next; // 将第二个链表的指针向后移动一位
        }
        // 如果第一个链表的当前节点的值和第二个链表的当前节点的值相等
        else {
            // 创建一个新节点，存储当前节点的值
            tail->next = (ListNode*)malloc(sizeof(ListNode));
            tail->next->val = p1->val;
            tail->next->next = NULL;
            tail = tail->next; // 将tail指针指向新节点，表示新链表的尾节点已经更新
            p1 = p1->next; // 将第一个链表的指针向后移动一位
            p2 = p2->next; // 将第二个链表的指针向后移动一位
        }
    }

    tail->next = NULL; // 将新链表的尾节点指向NULL，表示结束
    return head->next; // 返回新链表的头节点
}

int main() {
    ListNode* head1 = (ListNode*)malloc(sizeof(ListNode)); // 创建第一个链表的头节点
    head1->val = 1; // 设置第一个节点的值
    head1->next = (ListNode*)malloc(sizeof(ListNode)); // 创建第二个节点
    head1->next->val = 2; // 设置第二个节点的值
    head1->next->next = (ListNode*)malloc(sizeof(ListNode)); // 创建第三个节点
    head1->next->next->val = 3; // 设置第三个节点的值
    head1->next->next->next = (ListNode*)malloc(sizeof(ListNode)); // 创建第四个节点
    head1->next->next->next->val = 4; // 设置第四个节点的值
    head1->next->next->next->next = NULL; // 将最后一个节点的指针设置为NULL，表示结束

    ListNode* head2 = (ListNode*)malloc(sizeof(ListNode)); // 创建第二个链表的头节点
    head2->val = 2; // 设置第一个节点的值
    head2->next = (ListNode*)malloc(sizeof(ListNode)); // 创建第二个节点
    head2->next->val = 4; // 设置第二个节点的值
    head2->next->next = NULL; // 将最后一个节点的指针设置为NULL，表示结束

    // 调用函数获取两个链表的交集
    ListNode* head = getIntersectionNode(head1, head2);

    // 遍历新链表，输出所有节点的值
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }

    return 0;
}

在这个实现中，我们使用了动态内存分配来创建节点，需要在程序结束时手动释放申请的空间。我们也使用了一个虚拟头节点来简化代码，这个虚拟头节点的值可以是任意值，因为最终返回的是头节点的 next 指针。另外，我们还用 tail 指针来记录新链表的尾节点，这样就可以避免每次插入节点时都要遍历整个新链表找到尾节点。