题解 | 小红的方神题spj

#include <stdio.h>
#include<stdlib.h>

typedef struct List {
	int date;
	struct List* next;
}List;
//在位置i处添加一个数
int Add(List* L, int i, int e) {
	if (i < 1) {
		return 0;
	}
	List* p;
	int j = 0;
	p = L;//p存的是头节点的地址
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}
	if (p == NULL) {
		return 0;
	}
	List* s = (List*)malloc(sizeof(List));
	//date存放要存储的数据
	s->date = e;
	s->next = p->next;
	p->next = s;
	return 1;
}
//把单链表退化一遍
int Iterate(List* L) {
	if (L->date == 1) {
		return L->next->date;
	}
	List* begin = L->next;
	List* remember = NULL;
	int i = L->date;
	int before = 0;
	int after = 0;
	while (i - 1 > 0 && begin->next != NULL) {
		before = begin->date;
		after = begin->next->date;
		if (before > after) {
			begin->date = before - after;
		}
		else {
			begin->date = after - before;
		}
		remember = begin;
		begin = begin->next;
		i--;
	}
	//把链表最后一个位置的空间释放
	free(begin);
	//处理野指针
	remember->next = NULL;
	L->date--;
	return Iterate(L);
}
int main() {
	int n = 0;
	scanf("%d", &n);
	//创建一个头节点，date存放链表的长度
	List* head = (List*)malloc(sizeof(List));
	head->date = 0;
	head->next = NULL;
	for (int i = 1;i <= n;i++) {
		int e = 0;
		scanf("%d", &e);
		Add(head, i, e);
		head->date++;
	}
	printf("%d", Iterate(head));
	return 0;
}