设a和b是两个结点个数分别为m和n的单链表（带头结点），其中元素递增有序。设计一个尽可能高效的算法求a和b的交集，要求不破坏a、b的结点，将交集存放在单链表c中。给出你所设计的算法的时间复杂度和空间复

杂度。

算法思路：

1. 定义三个指针p、q、r，分别指向链表a、b、c的头结点。

2. 遍历链表a和b，比较a和b当前结点的值大小，如果相等，则将该结点插入到链表c中，并将p、q、r分别指向下一个结点；如果a当前结点的值小于b当前结点的值，则将p指向下一个结点；如果a当前结点的值大于b当前结点的值，则将q指向下一个结点。

3. 当p或q指向空结点时，算法结束。

算法时间复杂度为O(m+n)，空间复杂度为O(1)。

算法实现：

typedef struct Node {
    int data;
    struct Node *next;
} Node, *LinkedList;

LinkedList intersection(LinkedList a, LinkedList b) {
    LinkedList c = (LinkedList)malloc(sizeof(Node));
    c->next = NULL;
    Node *p = a->next, *q = b->next, *r = c;
    while (p && q) {
        if (p->data == q->data) {
            Node *node = (Node*)malloc(sizeof(Node));
            node->data = p->data;
            node->next = NULL;
            r->next = node;
            r = r->next;
            p = p->next;
            q = q->next;
        } else if (p->data < q->data) {
            p = p->next;
        } else {
            q = q->next;
        }
    }
    return c;
}