两个有序链表序列的交集【c++】

可以考虑使用双指针法来实现两个有序链表序列的交集。

具体实现思路如下：

1. 定义两个指针 p1 和 p2，分别指向两个有序链表的头结点。

2. 遍历两个链表，如果 p1 指向的节点的值小于 p2 指向的节点的值，则将 p1 向后移动一位；如果 p1 指向的节点的值大于 p2 指向的节点的值，则将 p2 向后移动一位；如果 p1 和 p2 指向的节点的值相等，则将该节点的值添加到结果链表中，同时将 p1 和 p2 向后移动一位。

3. 重复步骤 2，直到 p1 或 p2 指向了其中一个链表的尾节点，此时交集的求取已完成。

代码实现如下：

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

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }

    struct ListNode *p1 = headA, *p2 = headB;
    struct ListNode *res = NULL, *tail = NULL;

    while (p1 != NULL && p2 != NULL) {
        if (p1->val < p2->val) {
            p1 = p1->next;
        } else if (p1->val > p2->val) {
            p2 = p2->next;
        } else {
            struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
            node->val = p1->val;
            node->next = NULL;

            if (res == NULL) {
                res = node;
                tail = res;
            } else {
                tail->next = node;
                tail = tail->next;
            }

            p1 = p1->next;
            p2 = p2->next;
        }
    }

    return res;
}

需要注意的是，该方法只能求解两个有序链表的交集，如果要求解多个有序链表的交集，则需要使用其他算法。