对于两个有序无环单链表，求这两个链表的交集

比如：1>2>3>4>NULL 交 2>4>5>NULL => 2>4>NULL

在我之前提交的合并有序单链表上稍加改造即可。

struct node{
int data;
node* next;
};

typedef node* List;
List mergeSortedLinkList(List &list1, List &list2)
{
if (list1 == NULL)
{
    return list2;
}
if (list2 == NULL)
{
    return list1;
}
List pList1 = list1;
List pList2 = list2;
List mergedList = new node; //使用一个头节点，只是来指向合并好的链表，不存储数据
List pCurNode = mergedList;
while(pList1 && pList2)
{
    if (pList1->data < pList2->data)
        {
            pList1 = pList1->next;
        } 
        else if (pList1->data > pList2->data)
        {
            pList2 = pList2->next;
        }
        else
        {
        pCurNode->next = pList1;
        pCurNode = pList1;
        pList1 = pList1->next;
              pList2 = pList2->next;
        } 
}

return mergedList;
 }`enter code here`

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;
};

Node* Intersect(Node* head1, Node* head2)
{
    if(head1 == NULL || head2 == NULL)
        return NULL;
    Node* head = NULL;
    Node *cur = NULL;
    while(head1 != NULL && head2 != NULL)
    {
        if(head1->data < head2->data)
            head1 = head1->next;
        else if(head1->data > head2->data)
            head2 = head2->next;
        else
        {
            Node* node = new Node();
            node->data = head1->data;
            node->next = NULL;
            if(head == NULL)
                head = cur = node;
            else
                cur->next = node, cur = node;
            head1 = head1->next;
            head2 = head2->next;
        }
    }
    return head;
}

int main()
{
    Node* head1, *head2;
    head1 = head2 = NULL;
    int i;
    for(i = 4; i > 0; i--)
    {
        Node* node = new Node();
        node->data = i;
        node->next = head1;
        head1 = node;
    }
    int elem[] = {5, 4, 2};
    for(i = 0; i < 3; i++)
    {
        Node* node = new Node();
        node->data = elem[i];
        node->next = head2;
        head2 = node;
    }
    Node* head = Intersect(head1, head2);
    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    // 释放资源就不写了
}