LeetCode 206. Reverse Linked List

파이썬 알고리즘 인터뷰 문제 15번(리트코드 206번) Reverse Linked List
https://leetcode.com/problems/reverse-linked-list/

나의 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return
        prev = head
        curr = prev.next
        prev.next = None #처음에 이걸 안해서 루프 생김.

        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
            
        return prev

다른 풀이1

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev, curr = None, head

        while curr:
            prev, curr.next, curr = curr, prev, curr.next

        return prev

다른 풀이2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node, prev = None):
            if not node:
                return prev
            node.next, nxt = prev, node.next
            return reverse(nxt, node)
        return reverse(head, None)

오답, 배운 점

• 뒤집기는 흔한 유형이니 해결보다 우아하고 간결하게 작성하는 것에 익숙해지자.
• 처음에 지저분하게? 풀다가 시작 지점에 루프가 생기는 걸 생각하지 못했었음.
• 이 재귀는 처음 봤을 때 많이 헷갈렸다. return값이 그냥 쭉 전달되는 형태라서 그런가? 두 번 보니 좀 알겠다.
• 재귀는 여전히 아직 헷갈린다. 복습 필수!