연결 리스트 Q4. 짝수 노드를 뒤로 보내기

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

연결 리스트 Q4. 짝수 노드를 뒤로 보내기

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

Section A Linked List moveEvenItemsToBack

Q3과 같은 패턴이지만, 이번에는 짝수 값을 가진 노드만 골라 맨 뒤로 이동시키는 문제다. 문제가 바뀐 것은 필터 조건 하나뿐인데, 포인터 조작의 뼈대는 그대로 유지된다. 이런 반복을 통해 링크 재배선 패턴이 손에 들어온다.

한눈에 보는 문제 정보

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

대상 함수: moveEvenItemsToBack

카테고리: 연결 리스트

문제에서 요구한 것

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

• 1: Insert an integer to the linked list
• 2: Move all even integers to the back of the linked 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 even integers to the back of the linked list is

핵심 구현 흐름

STEP 1

원래 tail을 구해 순회 범위를 고정한다.

STEP 2

현재 노드가 짝수면 리스트 중간에서 분리하고 tail 뒤에 붙인다.

STEP 3

현재 노드가 홀수면 그대로 두고 다음 노드로 넘어간다.

핵심 코드

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

핵심 코드: moveEvenItemsToBack

void moveEvenItemsToBack(LinkedList *ll)
{
    if (ll == NULL || ll->head == NULL || ll->head->next == NULL)
            return;

        ListNode *cur = ll->head;      // 현재 짝수인지 홀수인지 검사할 녀석
        ListNode *prev = NULL;         // 항상 cur의 바로 앞을 쫓아다니는 녀석 (cur를 떼어낼 때 연결 끊어주기 위해 필요)
        ListNode *tail = ll->head;     // 짝수 발견하면 뒤에 붙여야 하니까 맨 끝 위치를 가리킬 녀석
    							       // 

        // 1. 진짜 꼬리(끝 노드) 찾기
        // 리스트 끝까지 쭈욱 돌아서 꼬리가 누군지 파악함
        while (tail->next != NULL)
            tail = tail->next;

        ListNode *oldTail = tail;      // 원래 리스트의 진짜 꼬리를 기억해 둠
                                       // 이걸 안 해두면 나중에 짝수를 뒤로 보냈을 때 다시 또 검사하면서 무한 루프에 빠짐...
        // 2. 본격적인 순회 시작 (단, 원래 리스트의 꼬리(oldTail)까지만 검사!)
        while (cur != NULL && cur != oldTail->next)
        {
            if (cur->item % 2 == 0)  // 오! 들어있는 값이 짝수다! 넌 뒤로 가라
            {
                ListNode *nextNode = cur->next; // 이 짝수를 떼어내면 이어붙일 다음 놈을 미리 기억해 둠

                // 일단 현재 위치에서 짝수 노드 떼어내기
                if (prev == NULL)        // 하필 맨 앞(head) 놈이 짝수였을 경우
                    ll->head = nextNode; // 머리를 두 번째 놈으로 바꿔버림 (기존 머리 싹둑)
                else                     // 중간 어딘가에 있는 놈이었을 경우
                    prev->next = nextNode; // 앞 놈이랑 뒷 놈을 바로 다이렉트로 연결 (가운데 짝수 싹둑)

                // 떨어져 나온 짝수 노드를 꼬리 뒤에 갖다 붙이기
                tail->next = cur;    // 기존 꼬리가 가리키는 다음 놈을 이 짝수 노드로 설정
                cur->next = NULL;    // 이제 얘가 맨 끝 노드니까 next에는 NULL 줘야 함
                tail = cur;          // 꼬리 위치 포인터를 새로 붙인 노드로 업데이트!

                // 검사할 타겟(cur) 이동
                // 짝수를 뽑아냈으므로, prev는 이동할 필요 없이 cur만 아까 기억해둔 nextNode로 이동시킴
                cur = nextNode;
            }
            else  // 홀수네 넌 그냥 원래 자리에 있어
            {
                prev = cur;          // 짝수가 아니니까 prev도 정상적으로 쫄래쫄래 따라감
                cur = cur->next;     // cur도 다음 놈 검사하러 이동
            }
        }
    }

    /*
    ===================================================================
    [ moveEvenItemsToBack 시각적 흐름도 ]

    예시: 1 -> 2 -> 3 -> 4 (4가 처음 파악한 oldTail)

    [초기 상태]
    Head -> [1] -> [2] -> [3] -> [4(oldTail)] -> NULL

    [Step 1] cur가 1을 가리킴 (홀수)
     -> 변화 없음, 다음 노드로 이동

    [Step 2] cur가 2를 가리킴 (짝수)
     -> 2를 떼어내서 현재 꼬리(4) 뒤에 연결!
    Head -> [1] -> [3] -> [4(oldTail)] -> [2(new tail)] -> NULL

    [Step 3] cur가 3을 가리킴 (홀수)
     -> 변화 없음, 다음 노드로 이동

    [Step 4] cur가 4를 가리킴 (짝수이자 oldTail 도달!)
     -> oldTail이었던 4도 떼어내서 현재 꼬리(2) 뒤에 연결!
    Head -> [1] -> [3] -> [2] -> [4(new tail)] -> NULL

    [최종 결과]  
    1 -> 3 -> 2 -> 4 -> NULL (홀수 먼저, 짝수 나중)
    ===================================================================
    */

    ///////////////////////////////////////////////////////////////////////////////////
}

구현할 때 체크할 점

• 짝수만 뒤로 보내는 동안 현재 노드와 이전 노드 갱신 순서를 잘못 잡으면 연결이 끊긴다.
• 노드 하나짜리 리스트는 그대로 종료하는 편이 안전하다.

마무리

이 문제는 거대한 알고리즘을 묻는 문제라기보다, 자료구조를 실제 포인터 연결과 순회 흐름으로 이해하고 있는지 확인하는 실습에 가깝다. 문제가 바뀐 것은 필터 조건 하나뿐인데, 포인터 조작의 뼈대는 그대로 유지된다. 이런 반복을 통해 링크 재배선 패턴이 손에 들어온다.

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