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

Linked List (6) - moveMaxToFront 함수 구현하기

리스트를 한 번 순회하면서 가장 큰 값을 가진 노드를 리스트의 맨 앞으로 이동시키는 함수.

주어진 요소 확인하기

구조체

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

moveMaxToFront 함수의 매개 변수

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

 

핵심 아이디어

• 연결 리스트를 순회해서 최대값(max_value)과 그 인덱스(max_idx)를 찾는다
  • 빈 리스트(*ptrHead == NULL)인 경우 순회가 불가능하므로, return -1 
  • max_idx가 0인 경우 노드를 이동시킬 필요가 없으므로, return 0
• 해당 최댓값 노드를 삭제
  • 현재 함수는 LinkedList 구조체 전체가 아니라 head 포인터만 이중 포인터로 전달받기 때문에,
    기존에 LinkedList *ll을 필요로 하는 removeNode() 같은 함수를 사용할 수 없다.
  • 따라서 head부터 순차적으로 삭제할 노드 직전 노드까지 접근해야 한다
• 저장해 둔 최대값을 0번 인덱스에 삽입
  • 새 노드를 할당하고, item에 max_value를 저장한다. 이후 이 노드의 next 필드를 기존의 head 노드 주소(*ptrHead)로 설정한다.
  • 마지막으로 *ptrHead를 새 노드로 변경하면 연결 리스트의 첫 번째 요소가 이 최대값 노드가 된다.

 

구현하기

int moveMaxToFront(ListNode **ptrHead)
{
    ListNode *cur = *ptrHead;
	if (cur == NULL) return -1;

	int i = 0;
	int max_idx = 0;
	int max_value = cur->item;
	while (cur != NULL) {
		if (cur->item > max_value) {
			max_idx = i;
			max_value = cur->item;
		}
		cur = cur->next;
		i++;
	}

	if (max_idx == 0) {
		return 0;
	}
	ListNode *pre = *ptrHead;
	i = 0;
	while (i < max_idx - 1) {
		pre = pre->next;
		i++;
	}
	cur = pre->next;
	pre->next = cur->next;
	free(cur);

	ListNode *new_head = malloc(sizeof(ListNode));
	new_head->item = max_value;
	new_head->next = *ptrHead;
	*ptrHead = new_head;

	return 1;
}