연결 리스트 Q6. 최댓값 노드를 맨 앞으로 옮기기

자료구조 C 실습 · 연결 리스트 · Q6

연결 리스트 Q6. 최댓값 노드를 맨 앞으로 옮기기

C 파일 하나를 문제 하나로 보고 정리한 풀이 글이다.
이번 글은 함수가 실제로 어떤 연결, 순회, 변환을 수행하는지에 초점을 맞춘다.

Section A Linked List moveMaxToFront

리스트 전체를 순회해 가장 큰 값을 가진 노드를 찾아 잘라낸 뒤, head 앞으로 옮기는 문제다. 최댓값 노드 자체뿐 아니라 그 바로 앞 노드도 기억해야 한다. 연결 리스트에서는 '앞 노드'를 잃는 순간 삭제와 이동이 모두 어려워진다.

한눈에 보는 문제 정보

원본 파일: C:\Users\cedis\OneDrive\문서\ANTIWORK\WEKK6~~~~~\data_structures_docker\Data-Structures\Linked_List\Q6_A_LL.c

대상 함수: moveMaxToFront

카테고리: 연결 리스트

문제에서 요구한 것

메뉴와 출력 문자열을 보면 이 파일은 특정 자료구조 연산 하나를 직접 구현하도록 만든 실습 문제다. 입력 흐름은 아래처럼 정리할 수 있다.

• 1: Insert an integer to the linked list
• 2: Move the largest stored value to the front of the list
• 0: Quit
• Input an integer that you want to add to the linked list
• The resulting linked list is
• The resulting linked list after moving largest stored value to the front of the list is

핵심 구현 흐름

STEP 1

전체를 순회하며 `maxNode`와 그 직전 노드 `maxPrev`를 함께 추적한다.

STEP 2

최댓값이 이미 head면 그대로 종료한다.

STEP 3

최댓값 노드를 분리해 head 앞에 연결하고 head를 갱신한다.

핵심 코드

문제 파일 전체를 다 옮기기보다, 실제로 구현해야 했던 함수만 뽑아서 보면 로직이 더 선명하게 들어온다.

핵심 코드: moveMaxToFront

int moveMaxToFront(ListNode **ptrHead)
{
	// 리스트가 아예 비어있거나 노드가 1개뿐이면 자리를 옮길 필요가 없으니 바로 종료!
	if (*ptrHead == NULL || (*ptrHead)->next == NULL)
		return 0;

    ListNode *cur = (*ptrHead)->next;  // 두 번째 노드부터 본격적으로 탐색할 예정
	ListNode *prev = *ptrHead;         // prev는 cur의 바로 직전 노드를 항상 쫓아감

	ListNode *maxNode = *ptrHead;      // 현재까지 발견된 가장 큰 값을 가진 노드 (일단 첫 번째 노드라고 가정)
	ListNode *maxPrev = NULL;          // 가장 큰 노드의 "직전 노드"를 기억해둬야 나중에 연결을 끊고 이어붙이기 가능

	// 끝까지 훑으면서 가장 큰 값과 그 앞 노드를 찾음
	while (cur != NULL)
	{
		if (cur->item > maxNode->item)  // 지금 본 노드가 기존 최댓값보다 크다면?
		{
			maxNode = cur;              // 최댓값 노드 갱신
			maxPrev = prev;             // 최댓값 앞 노드도 같이 갱신
		}
		prev = cur;                     // 다음 놈 검사하기 위해 쫄래쫄래 따라감
		cur = cur->next;                // 다음 놈으로 전진
	}

	// 만약 제일 큰 놈이 원래 맨 앞에 있던 놈이면 굳이 위치를 바꿀 필요가 없음!
	if (maxPrev == NULL)
    	return 0;

	// 이제 진짜 자리 옮기기 시작 (Max 노드를 파서 맨 앞으로)
	maxPrev->next = maxNode->next;      // 1. Max 앞 노드랑 Max 뒷 노드를 이어버림 (Max 분리!)
	maxNode->next = *ptrHead;           // 2. 떼어낸 Max 노드의 다음을 예전 맨 앞 노드(Head)로 연결
	*ptrHead = maxNode;                 // 3. 리스트의 새로운 머리(Head)를 Max 노드로 지정!

	return 0; // 함수가 int형 반환이라 대충 0 리턴 필수
}

구현할 때 체크할 점

• head가 최댓값일 때도 무조건 연결을 바꾸면 오히려 리스트를 망가뜨릴 수 있다.
• 직전 노드를 저장하지 않으면 최대 노드를 리스트 중간에서 떼어낼 수 없다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 최댓값 노드 자체뿐 아니라 그 바로 앞 노드도 기억해야 한다. 연결 리스트에서는 '앞 노드'를 잃는 순간 삭제와 이동이 모두 어려워진다.

같은 카테고리의 다른 문제와 함께 보면, 연결 리스트에서는 재배선, 스택과 큐에서는 순서 제어, 트리에서는 재귀 순회라는 감각이 반복해서 나온다는 점도 같이 볼 수 있다.