싱글 링크드 리스트 뒤집기

1. 전역 변수 head와 노드 포인터 prev, cur, next로 뒤집기

전체 코드

#include <stdio.h>
#include <stdlib.h>
struct Node {
	int data;
	Node* next;
};

Node* head = NULL;

void InsertAtHead(Node** phead, int x)
{
	Node* tmp = (Node*)malloc(sizeof(Node));
	tmp->data = x;
	tmp->next = NULL;

	if (*phead != NULL)
		tmp->next = *phead;

	*phead = tmp;
}

void Reverse()
{
	Node* prev = NULL;
	Node* cur = head;
	Node* next = NULL;

	while (cur != NULL)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	head = prev;
}

int main(void)
{

	InsertAtHead(&head, 5);
	InsertAtHead(&head, 4);
	InsertAtHead(&head, 3);
	InsertAtHead(&head, 2);
	InsertAtHead(&head, 1);

	Node* cur = head;
	while (cur != NULL)
	{
		printf("%d, ", cur->data);
		cur = cur->next;
	}

	printf("\n");

	Reverse();
	cur = head;
	while (cur != NULL)
	{
		printf("%d, ", cur->data);
		cur = cur->next;
	}

}

 

실행 결과

 

Reverse 함수

void Reverse()
{
	Node* prev = NULL;
	Node* cur = head;
	Node* next = NULL;

	while (cur != NULL)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	head = prev;
}

 

 

 

Reverse 함수 해설

Node* prev = NULL;
Node* cur = head;
Node* next = NULL;

prev는 NULL로, cur는 head로, next는 NULL로 설정합니다.

 

while (cur != NULL)
{
	next = cur->next;
	cur->next = prev;
	prev = cur;
	cur = next;
}

while문은 현재 노드 cur이 NULL이 아니면 계속 반복합니다.

 

다음 노드 next를 미리 cur을 이용해 저장합니다.

cur이 바뀔거기 떄문입니다.

 

현재 노드의 다음을 이전 노드로 설정합니다.

 

이제 다음 노드를 바꾸기 위한 준비를 합니다.

prev는 현재 노드 cur이 되고, cur은 next가 됩니다.

 

2. 매개변수로 뒤집기

Node* Reverse(Node* head)
{
	Node* prev = NULL;
	Node* cur = head;
	Node* next = NULL;

	while (cur != NULL)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}

int main()
{
	Node* head = NULL;
	head=Reverse(head);
}

 

3. 순환 함수

Node* Reverse(Node* p)
{
	if (p->next == NULL)
	{
		return p;
	}

	Node* r = Reverse(p->next);
	Node* q = p->next;
	q->next = p;
	p->next = NULL;
	return r;
}

int main(void)
{
	Node* head = NULL;
	InsertAtHead(&head, 5);
	InsertAtHead(&head, 4);
	InsertAtHead(&head, 3);
	InsertAtHead(&head, 2);
	InsertAtHead(&head, 1);
    
	head=Reverse(head);
    
}