개발하는데 다 이유가 있겠지

1. 홀수를 가진 노드를 뒤로 넣어 정렬하기

• 해결하지 못한 문제 분석하다가 홀수를 처리하는 과정에서 포인터를 이상한 곳에 지정해 세그멘테이션 폴트 발생
• 꼬리가 현재 노드(홀수)를 next로 가리킴
• 현재(홀수)의 전 노드가 현재(홀수)의 next를 가리킴
• 현재(홀수)의 next를 지움(NULL)
• cur를 이전 노드로 이동
• 꼬리 노드를 현재(홀수) 이동시킨 노드로 이동

void moveOddItemsToBack(LinkedList *ll)
{
	ListNode *cur, *prev, *tail;
	cur = ll->head;
	int size = ll->size;
	while (cur != NULL)
	{
		prev = cur;
		cur = cur->next;
		tail = prev;
	}

	cur = ll->head;
	prev = NULL;
	for (int i = 0; i < size; i++)
	{
		if (cur->item % 2 == 0)
		{
			prev = cur;
		}
		else
		{	
			// 꼬리가 현재(홀수)를 가리킴
			tail->next = cur;
			// 이전 노드가 현재(홀수)의 다음을 가리킴
			prev->next = cur->next;
			// 현재(홀수)의 다음을 지움 -> 꼬리가 되기 때문
			cur->next = NULL;
			// 현재를 이전 노드로 이동
			cur = prev;
			// 꼬리를 다음 노드(홀수)로 이동
			tail = tail->next;
		}
		cur = cur->next;
	}
}

---

2. 짝수를 가진 노드를 뒤로 넣어 정렬하기

• 위의 문제와 동일함
• 홀수를 뒤로 넘기는 것 대신에 짝수를 뒤로 넘김
• 홀수이면 그냥 넘기고
• 짝수이면 꼬리 노드 뒤로 이동시켜서 연결

void moveEvenItemsToBack(LinkedList *ll)
{
	ListNode *cur, *prev, *tail;
	cur = ll->head;
	int size = ll->size;
	while (cur != NULL)
	{
		prev = cur;
		cur = cur->next;
		tail = prev;
	}

	cur = ll->head;
	prev = NULL;
	for (int i = 0; i < size; i++)
	{	
    	# 홀수이면 넘어감
		if (cur->item % 2 != 0)
		{
			prev = cur;
		}
		else
		{
			// 꼬리가 현재(짝수)를 가리킴
			tail->next = cur;
			// 이전 노드가 현재(짝수)의 다음을 가리킴
			prev->next = cur->next;
			// 현재(짝수)의 다음을 지움 -> 꼬리가 되기 때문
			cur->next = NULL;
			// 현재를 이전 노드로 이동
			cur = prev;
			// 꼬리를 다음 노드(짝수)로 이동
			tail = tail->next;
		}
		cur = cur->next;
	}
}

---

3. 분기점을 기준으로 앞, 뒤 List 나누기

• 연결 리스트의 크기를 기준으로 짝수이면 2로 나누고, 홀수이면 2로 나누고 1을 더해서 분기점을 정함
• cur를 앞으로 전진하면서 분기점까지 전진하고 frontList의 head를 연결(분기점까지 도착)
• cur의 다음 지점에 backList의 head를 연결(분기점 이후에 연결)
• cur->next를 NULL로 바꿔 연결을 끊음(분리)

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
	ListNode *cur;
	// ll의 크기
	int size = ll->size;
	// 분기점
	int splitPoint = 0;
	cur = ll->head;

	// 짝수, 홀수에 따라 분기점 지정
	if (splitPoint % 2 == 0)
	{
		splitPoint = size / 2;
	}
	else
	{
		splitPoint = (size / 2) + 1;
	}

	// ll이 비었을 때
	if (size == 0)
	{
		resultFrontList->head = NULL;
		resultBackList->head = NULL;
		return;
	}

	// 분기점까지 cur을 진행시킴
	for (int i = 0; i < splitPoint; i++)
	{
		cur = cur->next;
	}
	// 프론트 리스트를 ll의 노드의 처음에 연결
	resultFrontList->head = ll->head;

	// 분기점 이후부터 백 리스트를 연결
	resultBackList->head = cur->next;

	// 분기점 완전 분리
	cur->next = NULL;
}

---

4. 최대 값을 List의 가장 앞으로 보내기

• 현재(cur), 이전(prev), 최대 값의 이전 노드(temp), 최대 값 노드(max)
• 2중 포인터를 이용해서 구현이 필요함
• ptrHead는 노드를 가리키는 포인터 head를 가리키는 포인터임
• max를 갱신하면서 max가 갱신될 때 max의 이전 노드를 temp에 저장해서 기억함
• cur와 prev를 cur이 NULL될 때까지 진행하면서 과정을 반복함
• 반복하고 max값 이전 노드인 temp의 next를 prev에 연결(cur이 NULL일때까지 탐색했기 때문에 prev는 마지막 노드를 가리킴)
  • 에러가 발생할 수도 있을 것 같음..?
• max의 next를 head로 연결(head는 첫 번째 노드의 주소를 가짐)
• head가 max를 가리키게 연결(*ptrHead는 head의 값을 가짐 -> head의 값은 첫 번째 노드의 주소임)

int moveMaxToFront(ListNode **ptrHead)
{
	ListNode *cur, *temp, *prev, *max = NULL;
	ListNode *head = *ptrHead;
	cur = head;
	max = head;
	while (cur != NULL)
	{
		if (cur->item > max->item)
		{
			max = cur;
			temp = prev;
		}
		prev = cur;
		cur = cur->next;
	}
	temp->next = prev;
	max->next = head;
	*ptrHead = max;
	return 0;
}

---

5. 재귀를 통한 리스트 뒤집기

• 이건 설명을 받았는데도, 이해가 잘 가지 않음
• 스택으로 쌓이는 과정을 그려가면서 풀어야 함
• 복습하기

void RecursiveReverse(ListNode **ptrHead)
{
	ListNode *first, *rest;
	if (*ptrHead == NULL)
		return;
	first = *ptrHead;
	rest = first->next;
	if (rest == NULL)
		return;
	RecursiveReverse(&rest);
	first->next->next = first;
	first->next = NULL;
	*ptrHead = rest;
}