【체인표】 선도 결점의 단방향 체인표 역순은 귀속과 비귀속을 포함한다

참조 링크

중요 함수

Link Reverse1(Link head)
{
	// ， ， 
	 Link prev = NULL;		//prev 
	 Link _head = head->next;	//_head 
	 Link next;

	 if(_head == NULL)
	 {
	 	return head;
	 }

	 while(_head)
	 {
	 	next = _head->next;
	 	_head->next = prev;
	 	prev = _head;
	 	_head = next;
	 }

	 head->next = prev;		// ， 
	 						// ！
	 return head;
}

// 
Link Reverse2_rec(Link head)
{
	Link new_head;

	if(head == NULL || head->next == NULL)
	{
		return head;
	}

	new_head = Reverse2_rec(head->next);
	head->next->next = head;
	head->next = NULL;

	return new_head;
}


Link Reverse2(Link head)
{
	head->next = Reverse2_rec(head->next);
	return head;
}

전체 함수

#include 
#include 

struct node
{
	int data;
	struct node *next;
};

typedef struct node Node;
typedef struct node * Link;

void CreateNode(Link *new_node)
{
	*new_node = (Link)malloc(sizeof(Node));
}

void CreateLink(Link *head)
{
	CreateNode(head);
	(*head)->next = NULL;
}

void InsertHead(Link head,Link new_node)
{
	new_node->next = head->next;
	head->next = new_node;
}

void Display(Link head)
{
	Link p = head;

	printf(" :
");
	if(p->next == NULL)
	{
		printf("Link is empty!
");
	}
	else
	{
		while(p->next != NULL)
		{
			p = p->next;
			printf("%d
",p->data);
		}
	}
}

Link Reverse(Link head)
{
	 Link p = head->next;
	 Link q;

	 if(p->next == NULL)
	 {
	 	return head;
	 }

	 p = p->next;
	 q = p->next;

	 head->next->next = NULL;

	 while(p != NULL)
	 {
	 	InsertHead(head,p);
	 	p = q;
	 	if(q != NULL)
	 	{
	 		q = q->next;
	 	}
	 }

	 return head;
}

Link Reverse1(Link head)
{
	// ， ， 
	 Link prev = NULL;		//prev 
	 Link _head = head->next;	//_head 
	 Link next;

	 if(_head == NULL)
	 {
	 	return head;
	 }

	 while(_head)
	 {
	 	next = _head->next;
	 	_head->next = prev;
	 	prev = _head;
	 	_head = next;
	 }

	 head->next = prev;		// ， 
	 						// ！
	 return head;
}

// 
Link Reverse2_rec(Link head)
{
	Link new_head;

	if(head == NULL || head->next == NULL)
	{
		return head;
	}

	new_head = Reverse2_rec(head->next);
	head->next->next = head;
	head->next = NULL;

	return new_head;
}


Link Reverse2(Link head)
{
	head->next = Reverse2_rec(head->next);
	return head;
}


int main()
{
	Link head;
	Link new_node;
	Link p;
	int i;
	int num;

	CreateLink(&head);

	for(i = 0; i < 6; i++)
	{
		CreateNode(&new_node);
		new_node->data = i + 1;
		InsertHead(head,new_node);
	}

	Display(head);

	Reverse1(head);

	Display(head);

	Reverse2(head);

	Display(head);

	return 0;
}