【问题描述】给定两个单链表，编写算法找出两个链表的公共结点。

1. wd-线性表54页----二（8）
   【问题描述】给定两个单链表，编写算法找出两个链表的公共结点。
   【输入形式】

四行：

第一行：一个数字（第一个单链表中的元素个数）

第二行：第一个单链表中各个结点的值

第三行：一个数字（第二个单链表中的元素个数）

第四行：第二个单链表中各个结点的值

【输出形式】

两行：

第一行：两个单链表的公共元素个数

第二行：依次打印输出各个公共元素
【样例输入】

6

12 5 8 9 -23 16

4

16 21 9 3
【样例输出】

2

9 16

注：若两个链表无公共元素，则输出：

0

无公共元素
【样例说明】
【评分标准】

用两个嵌套循环

这是引用的写法，供参考：

//************************ 引用的写法****************
#include <stdio.h>
#include <malloc.h>
// 链表节点结构
typedef struct Node {
    int data;
    struct Node* next;

}Node, * LinkList;
// 输出单链表
void show(LinkList L) 
{
    L->data == -1 ? NULL : printf(L->data == 0 ? "%d\n无公共元素" : "%d\n", L->data);
    Node* p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

LinkList findCommonNodes(LinkList L1, LinkList L2) 
{
    LinkList L = (Node*)malloc(sizeof(Node));
    L->data = 0;
    L->next = NULL;
    Node* p = L1->next, * pL = L;
    while (p) {
        Node* q = L2->next;
        while (q) 
        {
            if (p->data == q->data) {
                Node* f = (Node*)malloc(sizeof(Node));
                f->next = NULL;
                f->data = q->data;
                L->data++;
                pL->next = f;
                pL = f;
                break;
            }
            q = q->next;
        }
        p = p->next;
    }
    return L;
}

// 创建链表 
void createListFromHead(LinkList& L)
{
    Node* pL;
    int n, i;
    L = (Node*)malloc(sizeof(Node));// 创建头 
    L->data = -1;
    L->next = NULL;
    pL = L;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {// 生成链表 
        Node* p = (Node*)malloc(sizeof(Node));
        p->next = NULL;
        scanf("%d", &p->data);
        pL->next = p;
        pL = p;
    }
}

int main() 
{

    LinkList L1, L2, L = NULL;
    createListFromHead(L1);
    createListFromHead(L2);
    //show(L1);
    //show(L2);
    show(L = findCommonNodes(L1, L2));

    return 0;
}

再提供个纯指针的写法的：

//**************  指针版： 指针写法  ******************


#include <stdio.h>
#include <malloc.h>
// 链表节点结构
typedef struct Node {
    int    data;
    struct Node* next;
}Node, * LinkList;
// 输出单链表
void show(LinkList L)
{
    L->data == -1 ? NULL : printf(L->data == 0 ? "%d\n无公共元素" : "%d\n", L->data);
    Node* p = L->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
LinkList findCommonNodes(LinkList L1, LinkList L2)
{
    LinkList L = (Node*)malloc(sizeof(Node));
    L->data = 0;
    L->next = NULL;
    Node* p = L1->next, * pL = L;
    while (p) {
        Node* q = L2->next;
        while (q)
        {
            if (p->data == q->data) {
                Node* f = (Node*)malloc(sizeof(Node));
                f->next = NULL;
                f->data = q->data;
                L->data++;
                pL->next = f;
                pL = f;
                break;
            }
            q = q->next;
        }
        p = p->next;
    }
    return L;
}
// 创建链表 
void createListFromHead(LinkList* L)
{
    Node* pL;
    int n, i;
    (*L) = (Node*)malloc(sizeof(Node));// 创建头
    (*L)->data = -1;
    (*L)->next = NULL;
    pL = (*L);
    scanf("%d", &n);
    for (i = 0; i < n; i++) {// 生成链表
        Node* p = (Node*)malloc(sizeof(Node));
        p->next = NULL;
        scanf("%d", &p->data);
        pL->next = p;
        pL = p;
    }
}
int main()
{
    LinkList L1, L2, L = NULL;
    createListFromHead(&L1);
    createListFromHead(&L2);
    //show(L1);
    //show(L2);
    show(L = findCommonNodes(L1, L2));
   
    return 0;
}