7-1 两个有序序列的中位数 （25 分）

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A​0​​,A​1​​,⋯,A​N−1​​的中位数指A​(N−1)/2​​的值,即第⌊(N+1)/2⌋个数（A​0​​为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例1:

5
1 3 5 7 9
2 3 4 5 6

输出样例1:

4

输入样例2:

6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例2:

1

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
typedef struct Node* List;
struct Node {
	int self;
	List Next;
};
List creat(int cnt) {
	List head = new Node();
	List p = head,temp;
	int n;
	while (cnt) {
		cin >> n;
		temp = new Node();
		temp->self = n;
		p->Next = temp;
		p = p->Next;
		cnt--;
	}
	return head->Next;
}
int main()
{
	int n, cnt=0;
	cin >> n;
	List head1 = creat(n);
	List head2 = creat(n);
	while (head1 && head2) {
		if (head1->self > head2->self) {
			cnt++;
			if (cnt == n) printf("%d", head2->self);
			head2 = head2->Next;
			
		}
		else if (head1->self < head2->self) {
			cnt++;
			if (cnt == n) printf("%d", head1->self);
			head1 = head1->Next;
		}
		else {
			if (cnt + 1 == n || cnt + 2 == n) printf("%d", head1->self);
			cnt += 2;
			head2 = head2->Next; head1 = head1->Next;
		}
	}
	if (head1) {
		while (head1) {
			cnt++;
			if (cnt == n) printf("%d", head1->self); head1 = head1->Next;
		}
	}
	else {
		while (head2) {
			cnt++;
			if (cnt == n) printf("%d", head2->self); head2 = head2->Next;
		}
	}
}