[정글 WEEK05_C언어, 자료구조] Linked List 4번_moveEvenItemsToBack

 

TODO

짝수값을 가진 노드를 뒤로 보내기(moveEvenItemsToBack)

 

연결리스트 3번 - 홀수값을 가진 노드를 뒤로 보내기와 뒤로 보낼 노드가 짝수냐, 홀수냐를 제외하고는 동일한 문제이다.

3번 문제는 인덱스 기반으로 기존 함수를 호출해서 푼 관계로 성능 이슈가 있어서 이번 문제에서는 포인터 기반으로 구현했다. 

---

📦 구조체 분석

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;

 

 

🪄 기존 함수 분석

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

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

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

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

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

 

 

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

❗️먼저, 3번 문제의 성능 이슈 분석

  각 노드에 대해서 매번 리스트를 처음부터 순회하게 되어서 시간복잡도가 O(n^2)이다.

 

pseudocode

1. 포인터 변수 선언

   - cur: 현재 노드 주소. 매 반복마다 이동(cur=next)

   - prev: 현재 노드의 이전 노드 주소. 홀수 노드일 때만 이동(prev=cur)

   - next: 현재 노드의 다음 노드 주소

   - tail: 현재 연결리스트의 마지막 노드 주소

   - stop: 기존 연결 리스트의 tail의 다음 노드 주소 & while문의 종료조건

      • 리스트를 순회하면서 짝수 노드를 뒤로 보내는 경우 종료 조건이 없으면 반복문을 무한 반복하게 된다.

      • 하지만 초기 연결리스트의 마지막 노드까지만 순회해야한다.

      • 이때 기준이 되는 노드가 stop이고, cur가 stop의 다음 노드와 동일해질 때 루프를 종료한다.

2. cur == stop->next가 되어 연결 리스트 순회를 종료하기 전까지 아래 로직을 반복한다.

  2-1. 현재 노드 값이 짝수인 경우 연결 리스트에서 제거 후 tail 뒤에 붙인다.

     * tail의 다음 노드 주소를 cur로 갱신하는데, stop도 tail을 가리키기 때문에 stop의 다음 노드 주소도 cur이 된다.

     - 현재 노드가 head인 경우는 head 포인터를 next로 갱신하고,

     - 현재 노드가 head가 아닌 경우는 prev의 다음 주소로 next를 연결한다.

  2-2. 현재 노드 값이 홀수인 경우 현재 노드는 제거하지 않고 prev는 cur을 가리키고, cur은 next를 가리키도록 한 칸씩 이동한다.

 

💡 리스트를 한 번만 순회하므로 시간복잡도 O(n^2) → O(n)으로 개선

 

⌨️ 구현

void moveEvenItemsToBack(LinkedList *ll)
{
    if (ll == NULL) return;
    
    ListNode *cur = ll->head; // 현재 노드 주소
    ListNode *next; // 현재 노드의 다음 노드 주소
    ListNode *prev = NULL; // 현재 노드의 이전 노드 주소
    ListNode *tail = ll->head; // 현재 연결리스트의 마지막 노드 주소
    while (tail->next != NULL) {
        tail = tail->next;
    }
    ListNode *stop = tail; // 반복을 멈출 기점

    while (cur != stop->next) {
        next = cur->next;

        if (cur->item % 2 == 0) {
            if (cur == ll->head) {
                ll->head = next; // head 포인터를 next로 갱신 -> cur 제거
            } else {
                prev->next = next; // prev의 다음 포인터로 next 연결 -> cur 제거
            }

            // tail 뒤에 cur 붙이기
            tail->next = cur;
            cur->next = NULL;
            tail = cur;

            // cur은 next로 이동
            cur = next;
        } else {
            // 홀수라면 prev, cur 이동
            prev = cur;
            cur = next;
        }
    }
}

 

🧪 testcase

4 1 6 3 8

 

1️⃣ cur = 4

   • head 갱신 → head = 1

   • 4제거 → prev->next = 6

   • tail 뒤에 4 붙이고 tail 갱신 → tail = 4

   • prev는 그대로

   • stop->next = 4

변경 전:
[4] → [1] → [6] → [3] → [8] → NULL
 ↑cur  ↑next             ↑stop, tail

변경 후:
[1] → [6] → [3] → [8] → [4] → NULL
 ↑cur  ↑next       ↑stop ↑tail

 

2️⃣ cur = 1

   • 현재 노드 유지

   • prev = 1, cur = 6

   • stop->next = 4

변경 전:
[1] → [6] → [3] → [8] → [4] → NULL
 ↑cur  ↑next       ↑stop ↑tail
 
변경 후:
[1] → [6] → [3] → [8] → [4] → NULL
 ↑prev ↑cur  ↑next ↑stop ↑tail

 

3️⃣ cur = 6

   • 6 제거 → prev->next = 3

   • tail 뒤에 6 붙이고 tail 갱신 → tail = 6

   • stop->next = 4

변경 전:
[1] → [6] → [3] → [8] → [4] → NULL
 ↑prev ↑cur  ↑next ↑stop ↑tail

변경 후:
[1] → [3] → [8] → [4] → [6] → NULL
 ↑prev ↑cur  ↑next       ↑tail
             ↑stop

 

4️⃣ cur = 3

   • 현재 노드 유지

   • prev = 3, cur = 8

   • stop->next = 4

변경 전:
[1] → [3] → [8] → [4] → [6] → NULL
 ↑prev ↑cur  ↑next       ↑tail
             ↑stop

변경 후:
[1] → [3] → [8] → [4] → [6] → NULL
       ↑prev ↑cur  ↑next ↑tail
             ↑stop

 

5️⃣ cur = 8

   * cur==stop → 순회 계속

   • 8 제거 → prev->next = 4

   • stop->next = 4

   • tail 뒤에 8 붙이고 tail 갱신 → tail = 8

변경 전:
[1] → [3] → [8] → [4] → [6] → NULL
       ↑prev ↑cur  ↑next ↑tail
             ↑stop
             
변경 후:
[1] → [3] → [4] → [6] → [8] → NULL
       ↑prev ↑cur  ↑next ↑tail
                         ↑stop

 

6️⃣ cur = stop->next

   • 종료