연결 리스트 Q5. 앞/뒤 절반으로 분할하기

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

연결 리스트 Q5. 앞/뒤 절반으로 분할하기

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

Section A Linked List frontBackSplitLinkedList

원본 연결 리스트를 앞 절반과 뒤 절반으로 나누어 두 개의 결과 리스트를 만드는 문제다. 홀수 개라면 앞쪽이 하나 더 가진다. 노드를 새로 복사하는 방식으로도 풀 수 있지만, 지금 코드는 순회하면서 결과 리스트에 재구성하는 방식이라 size 계산과 분기 기준이 더 중요하다.

한눈에 보는 문제 정보

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

대상 함수: frontBackSplitLinkedList

카테고리: 연결 리스트

문제에서 요구한 것

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

• 1: Insert an integer to the linked list
• 2: Split the linked list into two linked lists, frontList and backList
• 0: Quit
• Input an integer that you want to add to the linked list
• The resulting linked list is
• The resulting linked lists after splitting the given linked list are

핵심 구현 흐름

STEP 1

원본 리스트 크기에서 `(size + 1) / 2`로 앞 리스트의 길이를 계산한다.

STEP 2

원본을 순회하면서 인덱스가 앞쪽 범위면 front, 아니면 back 리스트에 넣는다.

STEP 3

분할이 끝난 뒤 원본/결과 리스트의 head와 size를 확인한다.

핵심 코드

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

핵심 코드: frontBackSplitLinkedList

void frontBackSplitLinkedList(LinkedList *ll, LinkedList *resultFrontList, LinkedList *resultBackList)
{
    ListNode *cur = ll->head;              // 원본 리스트를 순회할 포인터
    int frontSize = (ll->size + 1) / 2;    // 앞쪽 리스트가 가져야 할 노드 개수 계산 (홀수일 경우 앞쪽이 하나 더 가짐)

    int i = 0;                             // 현재 순회 중인 노드의 인덱스를 추적할 변수

    while (cur != NULL)                    // 리스트의 끝까지 순회
    {
        if (i < frontSize)                 // 절반 이전의 노드라면
        {
            // 앞쪽 리스트의 끝(resultFrontList->size)에 현재 노드의 값을 삽입
            insertNode(resultFrontList, resultFrontList->size, cur->item);
        }
        else                               // 절반 이후의 노드라면
        {
            // 뒤쪽 리스트의 끝(resultBackList->size)에 현재 노드의 값을 삽입
            insertNode(resultBackList, resultBackList->size, cur->item);
        }

        cur = cur->next;                   // 다음 노드로 이동
        i++;                               // 인덱스 1 증가
    }
}

구현할 때 체크할 점

• 홀수 길이일 때 앞쪽이 하나 더 가져야 한다는 조건을 놓치기 쉽다.
• 원본 노드를 그대로 쓸지 새 노드를 만들지에 따라 메모리 해제 전략이 달라진다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 노드를 새로 복사하는 방식으로도 풀 수 있지만, 지금 코드는 순회하면서 결과 리스트에 재구성하는 방식이라 size 계산과 분기 기준이 더 중요하다.

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