[알고리즘] 단순 연결 리스트의 역순 연산

역순 연산

- 리스트의 노드들을 역순으로 만드는 연산

 

 

주의점

- 링크의 방향을 역순으로 바꾸기 전에 미리 뒤의 노드를 알아놓아야 한다. 

• 이 주의점이 이해가 안된다면 해당 포스트를 이해한 뒤 다시 보길 바란다.
• r q p 순으로 3개의 변수를 쓰는 이유는 역순으로 바꾸기 전 미리 뒤 노드의 정보를 알아놓기 위함이다. p의 뒤 노드는 p->link가 해결해준다.

 

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;
}

 

코드만 보면 굉장히 간단해 보이는데...꽤나 복잡하다..ㅠㅠ

 

연결 리스트는 위와 같다고 가정한다.

 

천천히 들여다보면

 

1) while 문을 들어가기 전 

p의 초기값 head 

q의 초기값 NULL

 

2) while문의 조건 -> p가 NULL이 아닐 동안 (결론적으로 역순으로 만들 것이기 때문에 p가 NULL이 되야 하고 q가 head가 되어야 함)

 

3) 첫번째 while 루프 후 변수 값

r = NULL

q = head

p =  20 

q->link = NULL

변수들이 r p q 순으로 자리를 잡았다. p의 시작 지점이 head이고 거꾸로 돌 것이다. head 앞에는 노드가 없기 때문에 NULL 값이 들어간 것이지 마지막 노드의 링크 필드 NULL과는 관계가 없다. 헷갈리지 말것! NULL 값을 그냥 쓰레기 값이라고 생각하는게 이해가 쉽다. 

 

현재 데이터필드가 10인 노드의 링크필드가 NULL이 되었다.

 

q값을 r한테 주고

p값을 q한테 주고

p->link 값은 p한테 주고

가운데 껴있는 p는 반대인 r쪽에게 링크필드를 넘겨준다. 

 

대충 while문이 돌아갈수록 이런 모양새가 나온다.

 

4) 두번째 while 문

 

r = head

q = 20

p =  30 

q->link = head

 

5) 세번째 while 문

 

r = 20

q = 30

p =  40 

q->link = 20

 

5) 네번째 while 문

 

r = 30

q = 40

p =  50 

q->link = 30

 

5) 다섯번째 while 문

 

r = 40

q = 50

p =  NULL 

q->link = 40

 

 

p가 NULL이 되었으므로 while문은 더이상 실행하지 않는다.

 

현재 구조를 q를 head로 보면 역순으로 연결 리스트가 완성된 모습을 볼 수 있다. 이제 자질구레한 것들 정리하고 다듬으면 아래와 같은 구조가 나타난다.

이제 q를 return 해주기만 하면 역순으로 완성된 리스트의 head 포인터가 반환된다.