예전에 지식인 답변으로 올려두었던 것인데, 파란 사이트가 폐쇄됨에 따라 답변 내용에 포함된 그림 파일이 다 날아가버렸다. 간혹 원문을 요청하시는 분이 있어서 이곳에 올려둔다. (지식인은 답변 완료된 게시물에 대해서는 수정이 불가하다. 그래서 불가피하게 이곳에 수정본을 올린다.)
< 지식인 질문 내용 >
기본적인 링크드 리스트를 다 이해했는데 역순만 이해를 잘 못하겟네요
삽입 삭제 등등..이런것은 매우 쉬운데 역순의 알고리즘이
왜 이렇게 되는지 모르겠습니다.
그냥 쏘스를 설명해달라는것이 아닙니다.
알고리즘에 대한 이해를 하고 싶습니다.
최대한 자세히 적어주시길 부탁 드릴께요.
제가 글을 읽어서 이해할수 있게 도와주시면 내공 드리겠습니다.
참고로 쏘스 올려봅니다.
ListNode *reverse(ListNode *head)
{
ListNode *p, *c, *n;
p = head;
n = null;
while ( p != NULL)
{
n = c;
c = p;
p = p->link;
c->link = n;
}return c;
}
ps.-_-적으면서도 이해가 되질 않으니 환장하것습니더...ㅜㅜ
< 이하 지식인 답변 내용 >
아무래도 이미지로 설명을 드리는게 가장 이해가 빠를것같아, 파워포인트로 그려봤습니다.
올리신 소스로 추정하여, Head와 Tail이 없는 단일 연결 리스트로 가정하였습니다.
ListNode *reverse(ListNode *head)
{
ListNode *p, *c, *n;
p = head;
n = null;
....
(이하생략)
일단 변수초기화 부분을 실행하면 아래와 같이 되겠지요.
 |
변수 p에는 Head를, n에는 null값을, c는 초기화하지 않았으므로 쓰레기주소값을 가집니다.
( 나중에 보시면 아시겠지만, 변수 c는 이곳에서 null로 초기화되어야 합니다 )
다음에 실질적인 while()문을 최초 실행하게 되면...
| while ( p != NULL) { (1) n = c; (2) c = p; (3) p = p->link; (4) c->link = n; } return c;  |
위와같이 변수의 값들이 변경됩니다.
그림설명을 잠깐 드리자면, 회색 화살표는 이전에 가리키던 값이고, 검은색화살표가 현재 변경된 값입니다. 코드에 적힌 숫자와 그림에 적힌 숫자를 매치하면서 살펴보시면 이해가 될 것입니다.
(3)번을 보시면, p = p->link 를 실행하는데, p는 현재 1번 노드를 가리키고 있고, p->link는 2번노드를 가리키므로, p = p->link 는 현재의 다음노드를 가리키라는 의미입니다.
(4)번 역시 (3)번과 일맥상통합니다. 이하 설명은 생략하고 이미지로 대신하도록 하겠습니다.
위의 그림이 좀 복잡하므로(화살표가 너무 어지럽죠?) 좀 정리를 해 보도록 하죠.
아래의 그림과 같습니다.
 |
이해 되시리라 생각합니다.
다시한번 while()문을 적용해보겠습니다.
 |
설명은 생략하겠습니다. 복잡한 위의 그림을 다시한번 정리해보도록 하겠습니다.
아래와 같습니다.
 |
다시 while()문을 적용합니다.
 |
다시 정리..^^;
 |
슬슬 끝이 보이는군요. ^^
다시한번 while()문을 적용토록 하겠습니다.
 |
정리 들어갑니다.
 |
이로서 완전한 리버스(Reverse)가 적용되었습니다. while()문의 조건이 p!=null 인데, 현재 p의 값이 null 이므로 루프를 빠져나와 c(리버스가 적용된 연결리스트의 헤드값)를 리턴하면서 함수는 종료합니다.
위의 그림을 보시면 아시겠지만, 마지막노드의 link가 쓰레기값을 가리키면서 끝나게 되지만 이는 잘못된 것입니다. 따라서 맨 처음에 언급드린 바와 같이, 변수 c또한 null값으로 초기화하는 코드가 필요하게 됩니다.
부디 이해되셨길 바랍니다. 수고하세요.
