c语言求链表A和链表B的交集(11)(12)
我觉得这两题是一样的,我就放在一起了
这个比并集要考虑的多一点,注意不能按顺序一个一个的比,有可能后面的也有和他相似的元素。
这道题我主要考虑了这样几个知识点
????以链表1的p为主要循环,当p到达尾部的时候,就循环查找结束
????如果两个相等的话,链表1和链表2的指针p,q都往后移,链表1的前驱指针移动到之前p的位置
????当元素不相等的时候,由于这两个都是递增序列,为了让其高效,我们要仔细考虑一下
????此时固定p指针,先判断此时q点的元素值是否大于p点的,如果大于的话,就证明后面也没有这些元素,此时就直接可以在链表1中删除这个元素,然后p指针后移,进行下一轮比较
????当固定p的时候,q循环到了末尾,此时证明链表2中元素都比p后面的元素小了,所以不可能有相同的元素了,就可以将prev->next置为NULL,结束循环
???? ???? ????哎 这道题我最后想了一想,其实也按照并集那样,对待大于和小于,不放在一起,也是比较之后再做决定,这样会比我现在这么复杂的思考要简单很多,这就大家自己实现啦~
代码
#include<stdio.h>
#include<stdlib.h>
//这里求的是交集 也就是只有相等的时候才插入到l1中
typedef struct node
{
int data;
struct node * next;
}Node;
typedef struct list
{
Node* head;
Node* tail;
}List;
void Init_list(List* L)
{
int length;
printf("please enter list length: ");
scanf("%d",&length); //scanf里面不能写类似于printf中打印字符串的语句
int number;
Node* first = (Node*)malloc(sizeof(Node));
if(!first)
printf("wrong!\n");
scanf("%d",&number); //在这里改一下就没有头节点了
first -> data = number;
first -> next = NULL;
L->head = L->tail = first;
for(int i = 1; i< length; i++)
{
Node* new = (Node*)malloc(sizeof(Node));
scanf("%d",&new -> data); //这个语句注意一下
new -> next = NULL;
L->tail -> next = new;
L->tail = new;
}
}
void merge(List* l1,List l2)
{
Node *p, *q,*save,*prev;
prev = l1->head;
p = l1->head -> next; q = l2.head -> next;
//用l1来存储新的链表
while(p)
{
if(q->data == p->data)
{
prev = p;
p = p->next;
q = q->next;
}
else
{
save = q; //保留q最初的地方
if(q->data > p->data) //找不到就删除节点
{
p = p->next;
prev -> next = p;
q = save;
}
else
{
q = q->next;
if(q == NULL)
{
prev -> next = NULL;
break; //找遍了也找不到的话,就后面都不用比较了
}
}
}
}
}
void print_list(List L)
{
Node* p;
p = L.head;
while(p != NULL)
{
printf("%d ",p->data);
p = p -> next;
}
printf("\n");
}
int main(int argc, char const *argv[])
{
List l1,l2;
Init_list(&l1);
Init_list(&l2);
merge(&l1,l2);
printf("after merge: ");
print_list(l1);
return 0;
}
运行截图: