[알고리즘] #Reverse Linked List

출처 : https://leetcode.com/problems/reverse-linked-list/

Reverse Linked List - LeetCode

문제

Reverse a singly linked list.

 

Example:

Input: 1->2->3->4->5->NULL

Output: 5->4->3->2->1->NULL

 

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

 

풀이

 

거꾸로 뒤집어야하니까 stack을 떠올렸다. stack의 push(), pop() 기능을 이용해서 LIFO로 풀고 싶었다.

일단, 주어진 리스트의 값들을 새로운 리스트에 담았고, pop() 메서드를 이용해서 값을 불러와서 새로운 ListNode를 만들었다.

 

결과는 성공했지만, 실행속도나 메모리 사용량을 보면 다른 코드들에 비해서 효율성이 떨어지는 편이었다.

내가봐도 일단 while 문이 두번이나 도니까 시간도 더 걸리고 메모리도 많이 사용하는게 문제였다.

 

 

 

다른 사람들이 짠 코드를 보니까 너무 간단...ㅠㅠ

위 코드 연산과정을 보면 아래와 같다.