DHU programming exercise

7 Find the intersection of ordered sequences （ Linked list ）

1. problem
Use the single linked list programming of the leading node ：

There are two ordered sequences , They represent two sets .

Find their intersection and output .

Be careful ： Here we need to use “ Orderly ” Characteristics of .
2. Enter description
The first line is the input sequence A Information about ：

The first integer n(0<=n<=100), Expressing common ownership n Elements , After that n It's an integer , Express n Data of elements

The first line is the input sequence B Information about ：

The first integer n(0<=n<=100), Expressing common ownership n Elements , After that n It's an integer , Express n Data of elements

notes ： Two sequences are input in order
3. The output shows that
Output a sequence of elements that intersect , See example for output format .

If the intersection is empty , The output “head–>tail”
4. Example
Input
4 1 3 5 7
4 1 4 5 8
Output
head–>1–>5–>tail
4. Code

#include<iostream>
using namespace std;
struct node

{
    
	int  data;
	struct node *next;
};

struct node* create(int n ,int num[])

{
    

	int i;

	struct node *current;// Current insertion position pointer 

	struct node *tail;// Tail pointer 

	struct node *head;// The head pointer 

	head = (struct node*)malloc(sizeof(struct node));// Head node 

	head->next = NULL;

	current = head;// The current position pointer points to the header node 

	tail = head;// The tail pointer also points to the head node 

	for (i = 0; i < n; i++)

	{
    
			struct node *p;

			p = (struct node*)malloc(sizeof(struct node));

			p->data = num[i];

			p->next = current->next;

			current->next = p;

			current = p;

			if (current->next == NULL) tail = current; // The current position is at the back , It needs to be modified tail The pointer 
	}

	return head;

}


int main()

{
    
	int a[101], b[101] ,n,i,m;
	struct node *L1, *L2;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	cin >> m;
	for (i = 0; i < m; i++)
		cin >> b[i];
	L1 = create(n, a);
	L2 = create(m, b);


	// seek L1,l2 Intersection 
	struct node *p, *q;
	p = L1->next;
	q = L2->next;
	cout << "head";
	while (p!=NULL&&q!=NULL)
	{
    
		if (p->data < q->data)
			p = p->next;

		else if (q->data < p->data)  // Pay attention to the logic here  ,if ,else if ,else
			q = q->next;

		else
		{
    
			cout << "-->" << p->data;
			p = p->next;
			q = q->next;
		}
	}
	cout << "-->tail" << endl;

	return 0;

}