[C언어] Linked List (7) - recursiveReverse함수 구현하기

Linked List (7) - recursiveReverse함수 구현하기

주어진 요소 확인하기

구조체

• LinkedList: (struct) 연결 리스트 구조체
  • size: (int field) 연결 리스트 요소 갯수
  • *head: (pointer field) 연결 리스트 첫 노드의 주소
• ListNode: (struct) 노드 구조체
  • item: (int field) 노드의 값
  • *next: (pointer field) 다음 노드의 주소

recursiveReverse 함수의 매개 변수

• **ptrHead: (double pointer) 연결 리스트 시작 노드 주소의 주소

 

핵심 아이디어

• 원래 연결 리스트의 끝 노드에 다다를 때까지 재귀적으로 다음 노드 이중 포인터(&nxt)를 넘긴다.
• 끝에 다다르면 끝에서부터 next 방향을 반대로 연결하면서 올라온다. (next->next = cur)
• 원래 연결 리스트의 시작 노드로 돌아오면 cur->next = NULL로 끝을 막아준다.
• 이후 *ptrHead, 곧 연결 리스트 첫 노드 주소를 원래 연결 리스트 끝 노드 주소(nxt)로 변경한다.
  • 재귀 함수들이 복귀하며 *ptrHead 값이 마지막 노드의 주소 값으로 연속해서 갱신됨

 

구현하기

void RecursiveReverse(ListNode **ptrHead)
{
	if (*ptrHead == NULL || (*ptrHead)->next == NULL) return;

	ListNode *nxt = (*ptrHead)->next;
	RecursiveReverse(&nxt);

	(*ptrHead)->next->next = (*ptrHead);
	(*ptrHead)->next = NULL;

	*ptrHead = nxt;
}