“파이썬 알고리즘 인터뷰” + https://leetcode.com/problems/reverse-linked-list/submissions/
계속되는 연결 리스트 문제. 오늘은 주어진 연결 리스트를 역전(reverse)해야한다. 난이도는 별 하나인데 나는 왜 몇 시간이나 헤매고 있는 걸까. 이해는 안 돼도 하나하나 따라가다보면 실력도 나아질 거라 생각했는데, 이런 문제도 풀지 못하고 있으면 나는 앞으로 어떻게 먹고 사나 하면서 온갖 자괴감에 시달리는 것이다.
[1,2,3,4,5]를 [5,4,3,2,1]로 만들면 된다. 어제까지 했던 다른 문제들처럼 재귀로 풀면 되겠다 싶어서 냉큼 돌려봤는데, 일반 리스트를 가정했던 탓인지 자꾸 무한반복으로 에러가 나고 말았다. 어제부터 계속 연결 리스트의 next 참조가 나를 힘들게 한다.
class Solution:
# 재귀
def reverseList1(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(node: ListNode, prev: ListNode = None) -> Optional[ListNode]:
if not node:
return prev
next, node.next = node.next, prev
return reverse(next, node)
return reverse(head)
# 반복
def reverseList2(self, head: Optional[ListNode]) -> Optional[ListNode]:
node, prev = head, None
while node:
next, node.next = node.next, prev
prev, node = node, next
return prev책에서는 위와같이 node와 prev를 동시에 넘기는 방식으로 되어 있지만 처음에 나는 그냥 next만 넘겨서 해결하려 했다. next가 끝까지 도달하면 반환하기 시작해서 역순 리스트를 만들어가는 식으로 하려 했지만 next링크를 내가 잘 파악하지 못한 것 같다. 될듯말듯 안 되는 상황. 결국 책에 있는대로 next, node.next = node.next, prev 에서처럼 다음 노드의 처리로 넘어가기 전에 현재 노드의 next를 prev로 바꿨다.(여전히 파이썬의 다중 할당은 익숙하지 않다.)
반복이 오히려 더 헷갈린다. 스왑을 하는 건 재귀랑 같지만 리턴하는 과정이 없으니 한참을 들여다 봐야했다.
게다가 더 재미 있는 건, 반복이 재귀보다 아주 약간이지만 더 빠르고 메모리도 덜 먹는다는 거다.