자료구조) 역순 연결 리스트(reverse linked list)

<들어가기에 앞서>

c언어로 작성된 코드입니다.

 

<역순 연결 리스트>

역순 연결 리스트(reverse linked list)는 단순 연결 리스트(singly linked list)를 거꾸로 역순으로 바꾼 연결 리스트이다. 

 

<소스 코드>

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

ListNode *reverse(ListNode *head) {     ListNode *p,*q,*r;       p = head;     q = NULL;       while (p != NULL)     {         r = q;         q = p;         p = p->link;         q->link = r;     }     return q; }   Colored by Color Scripter

cs

소스 코드를 여러번 봤지만 이해가 되지 않아 그림을 그려봤습니다.

 

 

<그림>

 

1) 포인터 p,q,r 을 선언하고 while( p! = NULL) 이전까지의 변화를 그림으로 나타냈습니다. 코드 순으로 그림에 1), 2)와 같이 표기하였습니다.

 

 

2) while문 scope을 첫 번째로 실행한 후의 모습입니다.

 

 

3) while문 scope을 두 번째로 실행한 후의 모습입니다.

 

 

4) while문 scope을 세 번째로 실행한 후의 모습입니다.

 

 

5)  while문 scope을 마지막으로 실행한 후의 모습입니다.

결국 ListNode *q가 가리키는 연결 리스트는  40 -> 30 -> 20 -> 10 -> NULL으로 바뀌게 되었고, 

매개변수인 ListNode *head의 역순이 되었습니다!!

 

 

<느낀 점>

처음에는 책을 봐도 이해가 되지 않았다.. 도무지 이해가 가지 않아 구글에 검색을 했다. 다행히 여러 자료들을 참고하여 코드 순서대로 그림을 그려보며 공부하니까 이해가 쏙쏙 되었다. 역시 구글 검색은 최고!! 

 

 

틀린 부분 있으면 피드백 부탁드립니다.

감사합니다. 좋은 하루 보내세요~!