#include <stdio.h>

struct node {int elem;struct node *next;};
typedef struct node* List;

List f4_1(List L)
{
	List p; int i;
	for (p = L, i = 0; p; i++, p = p->next);
	for (p = L, i /= 2; i; i--, p = p->next);
	return p;
}
List f4_2(List L, List M)
{
	List end = M;
	if (L) {
		for (; L->next != M; L = L->next);
		L->next = NULL;
	}
	if (M->next) {
		end = f4_2(NULL, M->next);
		M->next->next = M;
		M->next = NULL;
	}
	return end;
}
List f4_3(List L, List M)
{
	List p, S[100];
	int i = 0, j;
	
	for (; L->next != M; L = L->next);
	L->next = NULL;
	
	for (; M->next; S[i++] = M, M = M->next);
	
	for (p = M; i; p->next = S[--i], p = p->next);
	p->next = NULL;
	return M;
}

void show_list(char *msg, List L)
{
	printf(msg);
	printf("[ ");
	for (; L; L = L->next)
		printf("%d ", L->elem);
	printf("]\n");
}
void init_list(struct node nodes[], int len)
{
	int i;
	for (i = 0; i < len; i++) {
		nodes[i].elem = i;
		nodes[i].next = (List)NULL;
	}
	for (i = 0; i < len-1; i++) {
		nodes[i].next = &nodes[i+1];
	}
}

int main(void)
{
	struct node nodes[10];
	
	init_list(nodes, sizeof(nodes)/sizeof(nodes[0]));
	show_list("L = ", nodes);
	
	printf("Q1\n");
	show_list("L = ", f4_1(nodes));
	
	printf("Q2\n");
	show_list("L = ", nodes);
	show_list("M = ", f4_2(nodes, &nodes[4]));
	show_list("L = ", nodes);
	
	printf("Q3\n");
	init_list(nodes, sizeof(nodes)/sizeof(nodes[0]));
	show_list("L = ", nodes);
	show_list("M = ", f4_3(nodes, &nodes[4]));
	show_list("L = ", nodes);
}