7-52、两个有序链表序列的交集

刺骨的言语ヽ痛彻心扉 2022-10-27 01:36 134阅读 0赞

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

### 输入格式: ###

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

### 输出格式: ###

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出`NULL`。

### 输入样例: ###

1 2 5 -1
    2 4 5 8 10 -1

### 输出样例: ###

2 5

一开始用Java写了两遍，都无法全部通过，最后一个样例不是运行超时就是内存超限，有用Java通过的小伙伴们交流一下，本题无奈只能转C了。

思路：一对一比对，谁小谁next，尾插法创建链表，交集没有新建节点，而是取S1的节点，破坏了S1的链表。  
其他思路：使用一条S1链表即可，在S2输入数字的时候就进行比对，取交集，  
AC代码：

#include<stdio.h>
    #include<stdlib.h>
    typedef struct Node{
        
    	int value;
    	struct Node* next;
    }*Link; 
    
    Link createLink(){
        
    	Link head,tail,node;
    	int value;
    	head = (Link)malloc(sizeof(struct Node));
    	head->next = NULL;
    	tail = head;
    	while(scanf("%d",&value),value!=-1){
        
    		node = (Link)malloc(sizeof(struct Node));
    		node->value = value;
    		node->next = NULL;
    		tail->next = node;
    		tail = tail->next;
    	}
    	return head;
    }
    Link intersection(Link S1,Link S2){
        
    	Link S3,tail;
    	Link L1,L2;
    	if(S1 == NULL || S1->next == NULL || S2 == NULL || S2->next == NULL){
        
    		return NULL;
    	}
    	L1 = S1->next;
    	L2 = S2->next;
    	S3 = (Link)malloc(sizeof(struct Node));
    	S3->next = NULL;
    	tail = S3;
    	while(L1 != NULL && L2 != NULL){
        
    		if(L1->value > L2->value){
        
    			L2 = L2->next;
    		}else if(L1->value < L2->value){
        
    			L1 = L1->next;
    		}else{
        
    			tail->next=L1;
    			L1 = L1->next;
    			L2 = L2->next;
    			tail = tail->next;
    			tail->next = NULL;
    		}
    	}
    	return S3;
    }
    
    void print(Link S){
        
    	Link tail;
    	if(S == NULL || S->next == NULL) {
        
    		printf("NULL\n"); 
    		return ;
    	}
    	tail = S->next;
    	while(tail->next != NULL){
        
    		printf("%d ",tail->value);
    		tail = tail->next;
    	}
    	printf("%d\n",tail->value);
    }
    int main(){
        
    	Link S1,S2,S3;
    	S1 = createLink();
    	S2 = createLink();
    	S3 = intersection(S1,S2);
    	print(S3);
    	return 0;
    }