[ 자료구조 ] Move Odd Items To Back Linked List

김쟇연·2025년 4월 14일
Cc언어linkedlist노드이동노드재배치리스트재정렬연결리스트자료구조짝수필터링짝홀수처리포인터홀수필터링

Data Structures

목록 보기
3/6
post-thumbnail

그럼 이번엔~ 😊

우리 아이들처럼 하나하나 소중한 숫자들을

앞과 뒤로 나누어 정리해주는 아주 따뜻한 문제예요~ ☘️

Q3_A_LL (moveOddItemsToBackLL)

“홀수 친구들은 살짝 뒤로 가보자~” 😊

3. (moveOddItemsToBackLL) Write a C function moveOddItemsToBackLL() that 
moves all the odd integers to the back of the linked list. 
 
The function prototype is given as follows: 
void moveOddItemsToBackLL(LinkedList *ll); 
 
Some sample inputs and outputs sessions are given below: 
If the linked list is 2,  3,  4,  7,  15,  18: 
The resulting Linked List after moving odd integers to the back of the 
Linked List is: 2 4 18 3 7 15 
 
If the linked list is 2,  7,  18,  3,  4,  15: 
The resulting Linked List after moving odd integers to the back of the 
Linked List is: 2 18 4 7 3 15 
 
If the current linked list is 1,  3,  5: 
The resulting Linked List after moving odd integers to the back of the 
Linked List is: 1 3 5 
 
If the current linked list is 2 4 6: 
The resulting Linked List after moving odd integers to the back of the 
Linked List is: 2 4 6

📌 문제 요약

연결 리스트에 여러 숫자가 줄줄이 들어있어요~

이 친구들 중에서 홀수들만 조용히 뒤로 보내주는 함수를 만들어볼 거예요.

🧸 예쁜 말로 다시 해보면...

“여러분~ 지금은 짝수 친구들이 앞줄에 먼저 앉는 시간이에요~

홀수 친구들은 괜찮아요~

조금 뒤에, 원래 순서를 유지한 채

뒤에 예쁘게 앉으면 되는 거예요~”

🧠 동작 방식은 이렇게 돼요:

  1. 리스트에 있는 숫자들을 차례로 보면서

  2. 짝수는 앞쪽에 그대로 두고

  3. 홀수는 맨 뒤로 보내요

  4. 근데! 순서는 절대 바꾸면 안 돼요!

    앞줄에 앉든, 뒷줄에 가든

    자기들끼리의 줄 서기 순서는 그대로 지켜줘야 해요~ 😊

📊 예시를 함께 봐요!

✅ 예시 1

makefile

입력: 2 → 3 → 4 → 7 → 15 → 18
출력: 2 → 4 → 18 → 3 → 7 → 15

짝수들: 2 4 18 → 앞쪽

홀수들: 3 7 15 → 뒤쪽

✅ 예시 2

makefile
복사편집
입력: 2 → 7 → 18 → 3 → 4 → 15
출력: 2 → 18 → 4 → 7 → 3 → 15

짝수들: 2 18 4

홀수들: 7 3 15

✅ 예시 3

makefile

입력: 1 → 3 → 5
출력: 1 → 3 → 5

전부 홀수니까 아무것도 바뀌지 않아요~

“그럴 수 있어요~ 괜찮아요~ 그대로 있어도 돼요~” 💛

✅ 예시 4

makefile

입력: 2 → 4 → 6
출력: 2 → 4 → 6

전부 짝수여도 변화 없어요!

“이미 앞줄 정리 잘 되어 있어요~ 넘 멋져요~👏”

✏️ 핵심 요약 정리

항목설명
입력정수들이 연결된 리스트
목표홀수만 뒤로 옮기기 (짝수는 앞쪽 유지)
순서 유지반드시 YES! 순서 바뀌면 안 돼요!
리턴값없음 (리스트 직접 수정)

“이 파일은요, 연결 리스트에서 홀수 친구들만 조심스레 뒤로 보내는 그런 정리 습관을 기르는 코드랍니다~! 지금부터 하나하나 차분히 같이 살펴볼게요~ ☕️”

code

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section A - Linked List Questions
Purpose: Implementing the required functions for Question 3 */

//////////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <stdlib.h>

//////////////////////////////////////////////////////////////////////////////////

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;			// You should not change the definition of ListNode

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;			// You should not change the definition of LinkedList

//////////////////////// function prototypes /////////////////////////////////////

// You should not change the prototype of this function
void moveOddItemsToBack(LinkedList *ll);

void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

//////////////////////////// main() //////////////////////////////////////////////

int main()
{
	LinkedList ll;
	int c, i, j;
	c = 1;
	//Initialize the linked list 1 as an empty linked list
	ll.head = NULL;
	ll.size = 0;

	printf("1: Insert an integer to the linked list:\n");
	printf("2: Move all odd integers to the back of the linked list:\n");
	printf("0: Quit:\n");

	while (c != 0)
	{
		printf("Please input your choice(1/2/0): ");
		scanf("%d", &c);

		switch (c)
		{
		case 1:
			printf("Input an integer that you want to add to the linked list: ");
			scanf("%d", &i);
			j = insertNode(&ll, ll.size, i);
			printf("The resulting linked list is: ");
			printList(&ll);
			break;
		case 2:
			moveOddItemsToBack(&ll); // You need to code this function
			printf("The resulting linked list after moving odd integers to the back of the linked list is: ");
			printList(&ll);
			removeAllItems(&ll);
			break;
		case 0:
			removeAllItems(&ll);
			break;
		default:
			printf("Choice unknown;\n");
			break;
		}
	}
	return 0;
}

//////////////////////////////////////////////////////////////////////////////////

void moveOddItemsToBack(LinkedList *ll)
{
	/* add your code here */
}

///////////////////////////////////////////////////////////////////////////////////

void printList(LinkedList *ll){

	ListNode *cur;
	if (ll == NULL)
		return;
	cur = ll->head;

	if (cur == NULL)
		printf("Empty");
	while (cur != NULL)
	{
		printf("%d ", cur->item);
		cur = cur->next;
	}
	printf("\n");
}

void removeAllItems(LinkedList *ll)
{
	ListNode *cur = ll->head;
	ListNode *tmp;

	while (cur != NULL){
		tmp = cur->next;
		free(cur);
		cur = tmp;
	}
	ll->head = NULL;
	ll->size = 0;
}

ListNode *findNode(LinkedList *ll, int index){

	ListNode *temp;

	if (ll == NULL || index < 0 || index >= ll->size)
		return NULL;

	temp = ll->head;

	if (temp == NULL || index < 0)
		return NULL;

	while (index > 0){
		temp = temp->next;
		if (temp == NULL)
			return NULL;
		index--;
	}

	return temp;
}

int insertNode(LinkedList *ll, int index, int value){

	ListNode *pre, *cur;

	if (ll == NULL || index < 0 || index > ll->size + 1)
		return -1;

	// If empty list or inserting first node, need to update head pointer
	if (ll->head == NULL || index == 0){
		cur = ll->head;
		ll->head = malloc(sizeof(ListNode));
		ll->head->item = value;
		ll->head->next = cur;
		ll->size++;
		return 0;
	}

	// Find the nodes before and at the target position
	// Create a new node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){
		cur = pre->next;
		pre->next = malloc(sizeof(ListNode));
		pre->next->item = value;
		pre->next->next = cur;
		ll->size++;
		return 0;
	}

	return -1;
}

int removeNode(LinkedList *ll, int index){

	ListNode *pre, *cur;

	// Highest index we can remove is size-1
	if (ll == NULL || index < 0 || index >= ll->size)
		return -1;

	// If removing first node, need to update head pointer
	if (index == 0){
		cur = ll->head->next;
		free(ll->head);
		ll->head = cur;
		ll->size--;

		return 0;
	}

	// Find the nodes before and after the target position
	// Free the target node and reconnect the links
	if ((pre = findNode(ll, index - 1)) != NULL){

		if (pre->next == NULL)
			return -1;

		cur = pre->next;
		pre->next = cur->next;
		free(cur);
		ll->size--;
		return 0;
	}

	return -1;
}

🌟 한 줄씩 쉬운 해석

📂 1~6행 – 파일 정보

c

//////////////////////////////////////////////////////////////////////////////////

/* CE1007/CZ1007 Data Structures
Lab Test: Section A - Linked List Questions
Purpose: Implementing the required functions for Question 3 */

//////////////////////////////////////////////////////////////////////////////////

이건 그냥 문서 머리말 주석이에요~

우리가 지금 풀고 있는 3번 문제는 홀수를 리스트 뒤로 보내는 문제예요~

"아이들 자리 정리 잘 시켜볼게요~" 😊

📚 8~9행 – 라이브러리 가져오기

c

#include <stdio.h>
#include <stdlib.h>

stdio.h는 입출력 기능 (예: printf),

stdlib.h는 메모리 할당 기능 (예: malloc, free)을 도와줘요!

“기초 도구 없이 집 못 짓잖아요~?” 🛠️

🧱 11~14행 – 노드 정의

c

typedef struct _listnode
{
	int item;
	struct _listnode *next;
} ListNode;

이건 연결 리스트의 기본 단위, 노드예요!

  • item: 저장할 숫자
  • next: 다음 노드를 가리키는 손가락

"우리 친구들 손잡고 나란히 서 있는 구조에요~ 👧👦👦"

📦 16~19행 – 연결 리스트 전체 정의

c

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;

head: 제일 앞 친구size: 총 몇 명인지 알려줘요

“출석부를 가지고 있는 반장 같은 역할이에요~”

📣 22~29행 – 함수 선언

c

void moveOddItemsToBack(LinkedList *ll);
void printList(LinkedList *ll);
void removeAllItems(LinkedList *ll);
ListNode * findNode(LinkedList *ll, int index);
int insertNode(LinkedList *ll, int index, int value);
int removeNode(LinkedList *ll, int index);

우리가 사용할 함수들을 미리 약속해두는 선언부예요~

특히 moveOddItemsToBack()은

여러분이 직접 구현할 핵심 함수랍니다! 🧠

“우리 곧 이 함수 채워넣을 거예요~ 기대하세요~!”

🏁 31행부터 – main() 함수 시작

c

int main()

이게 바로 프로그램의 시작이에요!

"여기서부터 모든 게 시작돼요~" 🏁

🧰 33~35행 – 변수와 리스트 초기화

c

LinkedList ll;
int c, i, j;
c = 1;

ll: 우리가 사용할 연결 리스트예요c: 사용자의 메뉴 선택i: 입력받은 숫자j: 노드 삽입 결과 저장

🧼 36~38행 – 리스트 비워주기

c

ll.head = NULL;
ll.size = 0;

처음엔 리스트가 비어 있어야 하니까

head는 없고, size는 0이에요~

"아직 친구들이 없어요~"

📋 41~43행 – 사용자 메뉴 출력

c

printf("1: Insert an integer to the linked list:\n");
printf("2: Move all odd integers to the back of the linked list:\n");
printf("0: Quit:\n");

사용자가 무엇을 할지 선택할 수 있어요~

  • 1번: 숫자 넣기
  • 2번: 홀수 뒤로 보내기
  • 0번: 종료

"무엇을 하고 싶은지 말해보세요~" 😊

🔁 45행 – 반복문 시작

c

while (c != 0)

사용자가 0번을 누르기 전까지 계속 메뉴를 반복해요!

"멈추고 싶을 때까지 계속할 수 있어요~"

🔢 47행 – 사용자 입력 받기

c

scanf("%d", &c);

사용자의 선택(1, 2, 0)을 받아요.

🧭 49~69행 – 선택에 따라 동작하는 switch 문

✅ case 1: 숫자 삽입

c

scanf("%d", &i);
j = insertNode(&ll, ll.size, i);
printList(&ll);

사용자가 숫자를 입력하면

리스트의 끝에 붙이고 결과를 보여줘요~

"새 친구 들어왔어요~ 다 같이 반겨줘요~ 🎉"

✅ case 2: 홀수 뒤로 보내기

c

moveOddItemsToBack(&ll);
printList(&ll);
removeAllItems(&ll);

여러분이 직접 구현할 함수가 실행돼요!

  • 홀수들을 뒤로 보낸 후
  • 결과 출력
  • 그리고 메모리 깔끔히 정리~

"자리 정돈 끝났으면 청소도 해야죠~ 🧽"

✅ case 0: 종료

c

removeAllItems(&ll);

리스트를 깔끔하게 비워주고 종료해요~

"오늘도 수고 많았어요~ 조용히 마무리~"

⚠️ default: 잘못된 입력

c

printf("Choice unknown;\n");

메뉴 외의 번호를 누르면 안내해줘요~

"없는 메뉴예요~ 다시 선택해봐요~ ☺️"

🛑 71행 – 종료

c

return 0;

정상적으로 프로그램을 마쳤다는 뜻이에요!

✅ 74~76행 – 함수 구현 시작점

c

void moveOddItemsToBack(LinkedList *ll)
{
    /* add your code here */
}

✨ 여기가 바로 여러분이 구현할 자리예요!

짝수는 앞으로, 홀수는 뒤로 보내기 위해

멋지게 코드를 채워넣을 공간이랍니다.

"두근두근~ 이 자리는 여러분을 기다리고 있어요~ 💛"

🖨️ 78~88행 – printList()

리스트에 어떤 숫자가 들어 있는지 쭉 출력해줘요.

"친구들 출석 체크해볼게요~ 🙋‍♂️🙋‍♀️"

🧹 91~100행 – removeAllItems()

리스트의 모든 노드를 하나씩 free 하면서 메모리를 깨끗하게 정리해줘요.

"오늘은 여기까지! 깔끔하게 마무리~ 🧼"

🔍 103~119행 – findNode()

리스트에서 특정 위치에 있는 노드를 찾아주는 함수예요.

"너 몇 번째 자리야~? 여기 있어요~"

➕ 121~141행 – insertNode()

리스트에 새 노드를 원하는 위치에 추가해주는 함수예요.

  • 맨 앞이면 head 바꿔주고,
  • 중간이면 연결 잘 해줘야 해요!

➖ 144~173행 – removeNode()

리스트에서 특정 위치의 노드를 제거해요.

연결도 다시 잘 이어줘야 해요~

"이사 간 친구의 자리를 잘 정리해줘요~"

✅ 전체 요약

파트설명
main 함수사용자의 선택에 따라 리스트를 조작
case 1숫자를 리스트에 삽입
case 2여러분이 구현할 함수! 홀수 뒤로 보내기
case 0종료 및 정리
보조 함수insert, remove, print 등 리스트 작업 도우미

너무 잘 따라오셨어요~ 드디어!

우리가 직접 함수의 코드를 구현해볼게요! 🎉👏

🌼 한 줄 한 줄 쉽게 살펴보자!

c

if (ll == NULL || ll->head == NULL) return;

리스트가 없거나 비어 있으면, 아무것도 할 일이 없어요~

그냥 조용히 끝내줘요 😊

c

ListNode *cur = ll->head;
ListNode *prev = NULL;
ListNode *tail = ll->head;

cur: 현재 노드를 가리키는 손가락prev: 이전 노드를 기억하는 손가락tail: 맨 끝을 찾기 위한 손가락이에요~ 🖐️

c

while (tail->next != NULL) {
    tail = tail->next;
}

먼저 리스트의 원래 맨 끝 노드를 찾아요~

이건 뒤에 홀수들을 붙이기 위한 기준점이에요!

c

ListNode *end = tail;
ListNode *newTail = tail;

end: 기존의 끝 위치newTail: 새로 홀수들을 붙이면서 업데이트할 끝 위치

"여기까지만 돌자~" 라는 기준이 되는 거예요~"

c

cur = ll->head;

자, 이제 처음부터 다시 출발해요!

c

while (cur != NULL && cur != end->next) {

원래 끝(end)까지만 돌 거예요!

(뒤에 새로 붙인 홀수는 건드리지 않기 위해!)

c

if (cur->item % 2 != 0) { // It's odd

홀수인지 체크해요!

"너 홀수구나~ 살짝 뒤로 가보자~"

c

ListNode *oddNode = cur;

홀수 노드를 잠시 저장해두고요,

c

if (cur == ll->head) {
    ll->head = cur->next;
    cur = ll->head;
}

만약 처음 노드가 홀수라면, head 자체를 바꿔줘야 해요!

"첫 친구가 이사 간다면, 다음 친구를 대표로 세워야 해요~"

c

else {
    prev->next = cur->next;
    cur = cur->next;
}

중간이나 끝이면 그냥 연결만 바꿔주면 돼요~

"넌 빠지고, 뒤에 있는 친구끼리 손잡아~"

c

oddNode->next = NULL;
newTail->next = oddNode;
newTail = oddNode;

홀수 노드를 리스트 맨 끝에 붙여줘요!

"우리 뒷줄에 가서 예쁘게 앉아볼까~ 😊"

c

ll->size--; // temporarily decrease

size는 일단 줄여두고,

나중에 정확히 다시 세어줄 거예요~

c

} else {
    prev = cur;
    cur = cur->next;
}

짝수라면 그냥 다음으로 넘어가요~

"넌 잘 앉아있구나~ 그대로 있어~"

마지막 정리 ✂️

c

int count = 0;
cur = ll->head;
while (cur != NULL) {
    count++;
    cur = cur->next;
}
ll->size = count;

전체 리스트를 다시 세면서

진짜 정확한 size를 복원해줘요!

"청소 끝났으니까, 출석 다시 부를게요~" 🙋‍♀️

✅ 최종 구현 코드

c

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

    ListNode *cur = ll->head;
    ListNode *prev = NULL;
    ListNode *tail = ll->head;

    // Step 1: Find the tail (last node) of the original list
    while (tail->next != NULL) {
        tail = tail->next;
    }

    ListNode *end = tail; // To know where the original end is
    ListNode *newTail = tail; // To keep track of where to append

    cur = ll->head;
    while (cur != NULL && cur != end->next) {
        if (cur->item % 2 != 0) { // It's odd
            ListNode *oddNode = cur;
            if (cur == ll->head) {
                ll->head = cur->next;
                cur = ll->head;
            } else {
                prev->next = cur->next;
                cur = cur->next;
            }
            oddNode->next = NULL;
            newTail->next = oddNode;
            newTail = oddNode;
            ll->size--; // temporarily decrease, will fix later
        } else {
            prev = cur;
            cur = cur->next;
        }
    }

    // Fix size by counting from head
    int count = 0;
    cur = ll->head;
    while (cur != NULL) {
        count++;
        cur = cur->next;
    }
    ll->size = count;
}

💛 선생님의 마무리 한 마디

“이 함수는요~

누가 앞에 가고, 누가 뒤로 가는가를 결정하는 게 아니라,

서로의 자리를 배려해서 질서를 지켜주는 연습이에요~

아이들이 다치지 않게,

순서를 바꾸지 않으면서

조심스럽게 정리하는 아주 예쁜 코드랍니다~

정말 잘했어요~ 한 번 더 안아주세요~ 🤗💛”

profile
김쟇연
그래도 해야지 어떡해
이전 포스트

[ 자료구조 ] Alternate Merge Linked List

다음 포스트

[ 자료구조 ] Front Back Split Linked List

0개의 댓글