다음은 단순 연결 리스트(singly linked list) L에서 리… | [7급 국가직 자료구조론] 19년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 19년 1회차
다음은 단순 연결 리스트(singly linked list) L에서 리스트의 원소를 역순으로 바꾸는 함수이다. 함수에서 ㉠ 부분에 들어갈 프로그램 코드(code)로 옳은 것은?
typedef struct node{
struct node *link;
char data;
} listNode;
typedef struct{
listNode *head;
} linkedList;

void reverse(linkedList *L)
{
listNode *p, *q, *r;
p = L->head;
q = r = NULL;
while ( p != NULL) {
r = q;
q = p;
p = p->link;
㉠
}
L->head = q;
}
1
q = q->link;
2
q->link = r;
3
p->link = q;
4
r->link = q;
해설

㉠에는 q->link = r;가 들어간다.

반복마다 r은 이전 노드, q는 현재 노드, p는 다음 노드를 가리키도록 한 칸씩 이동한다. p를 미리 다음 노드로 옮겨 두었으므로 현재 노드 q의 링크를 이전 노드 r로 뒤집어도 나머지 리스트를 잃지 않는다.

반복이 끝나면 q가 원래의 마지막 노드이므로 L->head = q로 역순 리스트가 완성된다.

  • q = q->link;는 링크를 바꾸지 않고 포인터만 옮기므로 역순이 되지 않는다.
  • p->link = q;는 다음 노드의 링크를 바꿔 이후 노드를 잃게 되고, 마지막 반복에서 p가 NULL이면 오류가 난다.
  • r->link = q;는 이전 노드가 현재 노드를 가리키는 원래 방향 그대로이며, 첫 반복에서 r이 NULL이라 오류가 난다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 19년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기