题解 | 区间翻转

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

typedef struct Node {
	struct Node* before;
	struct Node* next;
	int data;
}Node;

typedef struct Queue {
	struct Node* left;
	struct Node* right;
	int length;
	int turn;
}Queue;

int main() {
	int n, k;
	scanf("%d %d", &n, &k);
	int left, right;
	Queue* head = (Queue*)malloc(sizeof(Queue));
	head->length = 0;
	head->turn = 1;
	int add = 1;
	int minus = 1;
	while (k--) {
		scanf("%d %d", &left, &right);
		if (left == right)continue;
		if (head->length == 0) {//空队列处理
			//添加第一个元素
			Node* s = (Node*)malloc(sizeof(Node));
			s->before = NULL;
			s->next = NULL;
			s->data = add++;
			head->left = s;
			head->right = s;
			head->length++;
		}
		//先把元素入列
		while (add <= right) {
			if (head->turn == 1) {//从队尾入队
				Node* s = (Node*)malloc(sizeof(Node));
				s->before = head->right;
				s->next = NULL;
				s->data = add++;
				head->right->next = s;
				head->right = s;
				head->length++;
			}
			else {//逆序从队头添加元素
				Node* s = (Node*)malloc(sizeof(Node));
				s->before = NULL;
				s->next = head->left;
				s->data = add++;
				head->left->before = s;
				head->left = s;
				head->length++;
			}
		}
		//把元素出列
		while (minus < left) {
			if (head->length == 0) break;//空队列结束循环，防止越界访问
			if (head->turn == 1) {//正序从队头出
				Node* p = head->left;
				printf("%d ", p->data);
				head->left = p->next;
				if (head->left) head->left->before = NULL;//处理野指针
				free(p);
				head->length--;
			}
			else {//逆序从队尾出列
				Node* p = head->right;
				printf("%d ", p->data);
				head->right = p->before;
				if (head->right)head->right->next = NULL;//处理野指针
				free(p);
				head->length--;
			}
			minus++;
		}
		head->turn *= (-1);
	}
	//输出队列中剩余的全部元素
	if (head->turn == 1) {//正序从队头输出
		Node* p = NULL;
		while (head->left) {
			p = head->left;
			printf("%d ", p->data);
			head->left = p->next;
			//head->left->before = NULL;
			free(p);
		}
	}
	else {
		Node* p = NULL;
		while (head->right) {
			p = head->right;
			printf("%d ", p->data);
			head->right = p->before;
			//head->right->next = NULL;
			free(p);
		}
	}
	//输出未反转过的元素
	while (add <= n) printf("%d ", add++);
	return 0;
}