[정글 WEEK05_C언어, 자료구조] Linked List 3번_moveOddItemsToBack

 

TODO

홀수값을 가진 노드를 뒤로 보내기(moveOddItemsToBack)

 

---

📦 구조체 분석

1. ListNode

: 연결리스트를 구성하는 노드

   - item: 해당 노드가 가지고 있는 int 타입 데이터

   - next: 다음 노드의 주소

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

 

2. LinkedList

: 연결 리스트

   - size: 연결 리스트가 가지고 있는 노드의 개수

   - head: 연결 리스트의 첫 번째 노드의 주소

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

 

 

🪄 기존 함수 분석

printList(LinkedList *ll): 연결 리스트 출력 

removeAllItems(LinkedList *ll): 모든 노드 삭제

findNode(LinkedList *ll, int index): 인덱스에 해당하는 노드 탐색

insertNode(LinkedList *ll, int index, int value): value를 값으로 가지는 노드 삽입

removeNode(LinkedList *ll, int index): 인덱스에 해당하는 노드 삭제

 

 

⚡️ 홀수값을 가진 노드를 뒤로 보내기 (moveOddItemsToBack)

pseudocode

1. index를 0으로 초기화해놓고 index가 연결 리스트 사이즈보다 작을 때까지만 아래 로직을 반복한다.

  1-1. 현재 노드를 찾는다.

  1-2. 현재 노드의 값이 홀수라면 해당 노드를 삭제 후 연결 리스트 맨 뒤에 해당 노드를 삽입한다. 

  1-3. 현재 노드의 값이 짝수라면 인덱스 + 1한다.

 

⌨️ 구현

void moveOddItemsToBack(LinkedList *ll) {
    // 노드를 하나씩 순회하면서 홀수이면 뒤로 보내기
    if (ll == NULL) return;

    int index = 0;
    int originalSize = ll->size;
	
    while (index < originalSize) {
        ListNode *node = findNode(ll, index);
        if (node == NULL) break;

        // 현재 노드(cur)의 값이 홀수라면 
        if (node->item % 2 != 0) {
            // 현재 노드 삭제: removeNode(cur)
            // 리스트 맨 뒤에 현재 노드 삽입: insertNode(cur)
            int value = node->item;
            removeNode(ll, index); // 현재 노드를 삭제하고 이전 노드의 next가 다음 노드를 바라보도록 
            insertNode(ll, ll->size, value);
        } else {
            index++; // 짝수일 때만 index 증가
        }
    }
}