Как поменять местами ноды стека/односвязного списка?

Question

[Sheogorath2]

Я хочу поменять местами ноды стека, содержащие минимальный и максимальный элементы.
В моём алгоритме когда мин. и макс. находятся рядом происходит зацикливание (нода указывает сама на себя).

#include <stdio.h>

struct Stack {
	int value;
	struct Stack *next;
};

void print_stack(struct Stack *head)
{
	struct Stack *h = head;
	if (h == NULL) return;
	while (h != NULL)
	{
		printf("%d at %p\n", h->value, h);
		h = h->next;
	}
}

struct Stack *swap_min_max_nodes(struct Stack *head)
{
	struct Stack *h = head;
	if (h == NULL) return head;
	struct Stack *min = h, *max = h;
	struct Stack *before_min = NULL, *before_max = NULL;
	while (h != NULL)
	{
		if (h->value < min->value) {before_min = min; min = h;}
		if (h->value > max->value) {before_max = max; max = h;}
		h = h->next;
	}

	if (before_min) before_min->next = max;
	if (before_max) before_max->next = min;

	struct Stack *tmp = min->next;
	min->next = max->next;
	max->next = tmp;

	struct Stack *new_head = head;
	if (new_head == min) new_head = max;
	if (new_head == max) new_head = min;
	return new_head;
}

int main(void)
{
	//struct Stack a    = {1,NULL};
	//struct Stack b    = {2,&a};
	//struct Stack head = {3,&b};
	struct Stack a    = {3,NULL};
	struct Stack b    = {1,&a};
	struct Stack c    = {4,&b};
	struct Stack head = {2,&c};
	print_stack(&head);
	struct Stack *new_head = swap_min_max_nodes(&head);
	printf("\n");
	print_stack(new_head);
	return 0;
}

Answer 1

[Wataru]

Ну да, вам придется рассматривать отдельный случай - когда они идут подряд. Проверяйте, что а вдруг min->next == max. Нарисуйте картинку из четырех точек before_min, min, max, max->next со стрелочками до помены и после. Смотрите у каких трех вершин ссылки поменяются и как. Запишите это в коде.

Еще есть случай max->next == min, но его можно рассмотреть вместе с предыдущим - просто в этом случае поменяйте месами указатели min и max (а также before_min и before_max). Тогда код для прошлого случая сработает. Вам же в момент помены без разницы, какая вершина максимум, а какая минимум. Вам надо только 2 заданные вершины поменять местами.

Comments

[Sheogorath2]

Спасибо, теперь понятно

struct Stack *tmp;
	if (max->next == min)
	{
		tmp = min;
		min = max;
		max = tmp;
		tmp = before_min;
		before_min = before_max;
		before_max = tmp;
	}
	if (min->next == max)
	{
		if (before_min) before_min->next = max;
		min->next = max->next;
		max->next = min;
	}
	else
	{
		if (before_min) before_min->next = max;
		if (before_max) before_max->next = min;

		tmp = min->next;
		min->next = max->next;
		max->next = tmp;
	}