다음 코드는 C 언어를 이용하여 주어진 연결 리스트 구조의 데이터에 대… | [7급 국가직 자료구조론] 21년 1회차 기출문제 상세 페이지

다음 코드는 C 언어를 이용하여 주어진 연결 리스트 구조의 데이터에 대한 삽입 정렬 함수를 구현한 것이다. ㉠ ～ ㉤에 들어갈 코드를 바르게 연결한 것은?
typedef struct _node {
  int data;
  struct _node *next;
}node;

void Insert(node **headRef, node *newNode) {
  if (*headRef == NULL ||
      (*headRef)->data >= newNode->data) {
    newNode->next = *headRef;
    *headRef = newNode;
  }
  else {
    node *current = *headRef;
    while (current->next != NULL &&
           current->next->data < newNode->data){
           ( ㉠ )
    }
    ( ㉡ )
    ( ㉢ )
  }
}

void Sort(node **headRef) {
  node *result = NULL, *current = *headRef;
  node *next;
  while (current!=NULL) {
    ( ㉣ )
    Insert(&result, current);
    ( ㉤ )
  }
  *headRef = result;
}
A : current->next = current;
B : current = current->next;
C : current->next = newNode;
D : next = current->next;
E : current->next = next;
F : current = next;
G : newNode->next = current->next;
㉠　　㉡　　㉢　　㉣　　㉤

A　　D　　E　　F　　G

B　　G　　C　　D　　F

C　　E　　B　　A　　D

E　　G　　B　　F　　A

㉠~㉤은 차례로 B, G, C, D, F이다. Insert는 newNode가 들어갈 자리의 직전 노드를 찾아 끼우고, Sort는 원래 리스트에서 노드를 하나씩 떼어 정렬된 result에 삽입한다.
Insert: 다음 노드 값이 newNode보다 작은 동안 current = current->next(B)로 전진한다. 멈춘 뒤 newNode->next = current->next(G)로 뒤쪽을 먼저 잇고, current->next = newNode(C)로 앞쪽을 연결한다.
Sort: Insert가 current->next를 바꾸므로 그 전에 next = current->next(D)로 다음 노드를 먼저 저장하고, 삽입 후 current = next(F)로 이동한다.
㉠에 current->next = current(A)를 넣으면 노드가 자기 자신을 가리켜 while문이 끝나지 않는다.
㉠에 current->next = newNode(C)를 넣으면 탐색 도중 연결을 덮어써 뒤쪽 노드를 잃는다.
㉠에 current->next = next(E)를 넣으면 Insert 안에 없는 변수 next를 쓰게 되어 성립하지 않는다.