欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求两个元素递增排列的链表的交集,并将其存放在某个链表中

程序员文章站 2022-03-10 12:09:00
...
#include "stdafx.h"
#include<stdio.h> 
#include<malloc.h> 
#include<stdlib.h>
typedef int type;
typedef struct lnode //定义链表结点的数据结构 
{
    int data;
    struct lnode *next;
}Lnode;
typedef Lnode node;
typedef struct dnode//定义双链表结点的数据结构 
{
    int data;
    struct dnode *lnext;
    struct dnode *rnext;
}Dnode;
bool isposorder(node *h)//判断链表元素排列是否正序
{
    node *p = h->next;
    while (p->next)
    if (p->next->data<p->data)
        return false;
    else
        p = p->next;
    return true;
}
int comele15(node *h1, node *h2)
{
    //从h1第一个元素开始进行删除,删除再h2中不存在的元素,直到遍历到h1的末尾,
    //为了充分利用有序的条件,应使h1,h2遍历一遍即可
    if (!(isposorder(h1) && isposorder(h2)))
        return -1;
    node *p = h1;
    node *q = h2->next;
    while (q&&p->next)
    {
        node *tem;
        if (p->next->data < q->data)
        {
            tem = p;
            while (p->next&&p&&p->next->data < q->data)
                p = p->next;
            if (!p->next)//此处防止p只剩一个元素而要去访问p->nex->next的错误情况而直接退出
            {
                tem->next = p->next;
                break;
            }
            if (p->next->data == q->data)
                tem->next = p->next;
            else
            {
                tem->next = p->next->next;
                p = p->next;
            }
        }
        else if (p->next->data == q->data)
        {
            p = p->next; q = q->next; tem = p;
        }
        else        
            while (p->next&&q&&p->next->data > q->data)     
                q = q->next;
    }
    p->next = NULL;
    return 0;
}