1. 문제
leetcode 206. Reverse linked list
한방향 연결리스트 head가 주어지면, 이를 뒤집어서 리턴하여라.
2. 반복을 이용한 내 풀이
현재노드 head, 이전노드 prev를 이용해 리스트의 끝까지 탐색하며 연결의 방향을 바꾸었다. 먼저, head 뒤 노드를 가리키는 포인터 prev를 만든다. 그리고 리스트가 종료되어 head가 None이 될 때까지 prev와 head를 한칸씩 앞으로 옮기며 리스트를 탐색한다. 동시에 이전에 prev에 있었던 노드를 현재 앞으로 옮겨진 prev가 가리키게 하며 리스트 연결의 방향을 바꾼다. 리스트 탐색이 종료되면 뒤집어진 리스트의 시작부분인 prev를 리턴한다.
이 방법으로 실행속도와 메모리 사용량 모두 상위 1.56%를 달성하였다.
3. 재귀를 이용한 풀이
현재 노드와 이전 노드를 인자로 받는 재귀함수 reverse를 이용해 문제를 풀 수도 있다. 이 함수는 현재노드 node에서 이전노드 prev로 향하는 연결을 만든다. 그리고 node, prev를 한칸씩 앞으로 옮겨서 자기 자신을 호출한다. 함수는 리스트 탐색이 종료되어 node가 None이면 종료되고, 뒤집어진 리스트의 시작이 된 prev를 리턴한다.
'Computer Science > 알고리즘' 카테고리의 다른 글
| [파이썬 알고리즘] DFS와 BFS를 이용한 그래프 탐색 (0) | 2022.02.18 |
|---|---|
| [파이썬 알고리즘] 16. 페어의 노드 스왑 (0) | 2022.02.16 |
| [파이썬 알고리즘 인터뷰] 13. 두 정렬 리스트의 병합 (0) | 2022.02.13 |
| [파이썬 알고리즘 인터뷰] 12. 팰린드롬 연결리스트 (0) | 2022.02.13 |
| [파이썬 알고리즘 인터뷰] 11. 주식을 사고팔기 가장 좋을 때 (2) | 2022.02.12 |
