Reverse Loop 방식

1. head 노드에서 시작한다.
   
2. current 노드를 다음 노드로 이동시킨다.

3. current 노드(2)의 next가 front(1)를 가리키게 변경하고, current 노드를 이동시킨다.
   
4. current 노드(3)의 next가 front(2)를 가리키게 변경하고, current 노드를 이동시킨다.
   
5. current 노드(4)의 next가 front(3)를 가리키게 변경하고, current 노드를 이동시킨다.
   
6. current 노드(5)의 next가 front(4)를 가리키게 변경하고, current 노드를 이동시킨다.
   
7. head 포인터가 5를 가리키게 설정한다.
   

구현 코드

void LoopReverse(ListNode **ptrHead)
{
	ListNode *front = NULL;
	ListNode *cur = *ptrHead;
	ListNode *next;

	while (cur != NULL)
	{
		next = cur->next;
		cur->next = front;
		front = cur;
		cur = next;
	}
	*ptrHead = front;
}

Reverse Recursive 방식

재귀를 사용하여 역순으로 만들면 리스트의 끝까지 간 뒤에 포인터를 바꿔주는 방식으로 메모리 이동이 필요없다.

순서대로 따라가보자.

1. head→next→next가 NULL이 되었다. 현재 head는 4이다.

   리스트의 끝에 도달했기 때문에 tail 노드의 주소를 저장해두고(마지막에 head 주소 반영해야 함) 리스트 방향 전환을 시작한다.

   

2. 연산을 완료하여, 이전 head 3으로 돌아간다.
   

3. 쭉 반복한다.

   

4. head를 저장해둔 리스트의 끝, tail로 재설정 해준다.

   

구현 코드

void RecursiveReverse(ListNode **ptrHead)
{
	ListNode *head = *ptrHead;

	// base case: 비어있거나 하나 남았다면
	if (head == NULL || head->next == NULL)
		return;

	// 재귀 호출, 나머지 리스트를 뒤집음
	ListNode *tail = head->next; // 끝 노드 저장
	RecursiveReverse(&tail);

	// 연결을 뒤집음
	head->next->next = head;
	head->next = NULL;

	// 역순 리스트의 새로운 head를 반영
	*ptrHead = tail;
}