1 题目

/**
 * 两个有序的无头结点的链表La，Lb。
 * 编写函数：如何以最优的方式找出二者的交集，并且把结果存在一个新链表中返回。
 */

2 题解

2.1 解题思路

这道题求解的是两个有序链表的交集（区别于共同节点，这里只要求数值相同即可），注意有序字眼。

构造第三个链表C，指针aa，bb，cc分别指向带查询的两个链表A和B以及链表C。

两个有序链表涉及合并、交集、去重复基本上都可以使用双指针指向，小的往前移动，遇到相同的则复制到链表C中，直到一方指向为空则完成该过程。

2.2 解题图示

2.3 结果图示



2.4 结果分析

时间复杂度：O(n)，空间复杂度：O(n)

2.5 代码

LinkList intersection(LinkList a,LinkList b){
    LinkList c;
    initLinkList(c);
    LinkList aa = a->next,bb=b->next,cc = c;
    while (aa && bb){
        if (aa->data == bb->data){
            Node* node = new Node();
            node->data = aa->data;
            node->next = NULL;
            cc->next = node;
            cc = cc->next;
            aa = aa->next;
            bb = bb->next;
        } else if (aa->data < bb->data){
            aa = aa->next;
        } else{
            bb = bb->next;
        }
    }
    return c;
}