求序列的交集（链表）

问题描述 :

使用带头结点的单链表编程：

有两个序列，分别表示两个集合。

求它们的交集并输出。

输入说明 :

第一行输入序列A的信息：

第一个整数n(0<=n<=100)，表示共有n个元素，其后有n个整数，表示n个元素的数据

第一行输入序列B的信息：

第一个整数n(0<=n<=100)，表示共有n个元素，其后有n个整数，表示n个元素的数据

输出说明 :

输出交集的元素序列，输出格式见范例。

如果交集为空，则输出“head-->tail”

交集里的元素顺序，依照其在序列A中的顺序。

比如：

序列：

A：5 3 2 7

B：1 3 5 8

则交集为5和3，因为在序列A中，5在3的前面，所以在交集里5也在3的前面。

输入范例 :

4 5 3 2 7
4 1 3 5 8

输出范例 :

head-->5-->3-->tail

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
struct student
{
    int  num;
    struct student* next;
};
struct student* createByTail(int size)
{
    struct student* head;
    struct student* p1, * p2;
    int n;
    n = 0;
    p1 = p2 = (struct student*)malloc(sizeof(struct student));
    scanf("%d", &p1->num);
    head = NULL;  //首先置链表为空链表
    while (p1->num != -1)    //num为-1，意味着用户输入结束
    {
        n = n + 1;
        if (n == 1)            //创建第一个结点
            head = p1;
        else
            p2->next = p1;
        p2 = p1;            //p2始终指向最后一个结点（即尾指针）
        if (size == n)break;
        p1 = (struct student*)malloc(sizeof(struct student)); //p1指向新结点
        scanf("%d", &p1->num);
    }
    p2->next = NULL;  //切记：最后一个结点的next赋值为NULL
    return head;
}
//输出链表中的信息（num）
void  displayLink(struct student* head)
{
    struct student* p;
    p = head;
    printf("head-->");
    while (p != NULL)
    {
        printf("%d-->", p->num);
        p = p->next;
    }
    printf("tail
");
}
//求L1 L2的交集 按L1的顺序排
//对于L1的每个元素 如果L2没有则删除 
struct student* intersection(struct student* L1, struct student* L2)
{
    struct student* pl2 , * pl1=L1, * q, * pl1_pre=NULL;
    while (pl1)
    {
        pl2 = L2;
        while (pl2&& pl2->num != pl1->num)
            pl2 = pl2->next;
        if (pl2 && pl2->num == pl1->num)//L2中有
        {
            pl1_pre = pl1;
            pl1 = pl1->next;
        }
        else//L2中没有 则删除
        {
            if (pl1 == L1)//是头
            {
                q = pl1;
                L1 = pl1->next;
                free(q);
                pl1_pre = NULL;
                pl1 = L1;
            }
            else//不是头
            {
                q = pl1;
                pl1_pre->next = pl1->next;
                free(q);
                pl1 = pl1_pre->next;
            }
        }
    }
    return L1;
}
int main()
{
    struct student* headA, * headB;
    int i = 0, n;
    scanf("%d", &n);
    headA = createByTail(n);
    //displayLink(headA);
    scanf("%d", &n);
    headB = createByTail(n);
    //displayLink(headB);
    displayLink(intersection(headA, headB));
    return 0;
}