문제

• singly linked list의 head가 주어짐
• reverse하라

풀이

• recursion
• 머리에서 꼬리로 내려갔다가, 다시 올라오면서 next를 바꿔줌
• isOriginalHead boolean 변수를 둬서, 원래 머리 즉, 새로운 꼬리는 next = None 으로 처리해줌

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head:
            global newHead
            solution(head, True)
            return newHead
        else:
            return None


def solution(thisNode, isOriginalHead):
    global newHead
    if not thisNode.next:  # if None
        newHead = thisNode
        return newHead
    preNode = solution(thisNode.next, False)  # go down to tail
    preNode.next = thisNode  # when come up, reverse
    if isOriginalHead:
        thisNode.next = None
    return thisNode

• 사실 처음에 recursion하면 느릴것 같아서 stack을 이용하려했는데, 메모리 초과로 실패했다

결과