Reverse Linked List

단방향 연결 리스트를 뒤집는 문제

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList( self, head: ListNode ) -> ListNode:
        if head is  None:
            return head
        else:
            reversedHead, _ = self.__reverseListIteratively( head )
            head.next = None

            return reversedHead


    def __reverseListIteratively( self, head ):
        if head is None:
            return None, None
        else:
            reversedHead, reversedTail = self.__reverseListIteratively( head.next )

            if reversedTail is None:
                return head, head
            else:
                reversedTail.next = head

                return reversedHead, head


    def __reverseListRecusively( self, head, otherHead = None ):
        '''연결 리스트의 말단까지 들어가면서 연결을 뒤집는다
        '''
        if head is None:
            return head
        else:
            newHead = head.next

            # 말단에 도달했으면 이전 노드를 말단으로 삼는다
            if newHead is None:
                head.next = otherHead

                return head
            else:
                # 처음으로 탐색했으면 첨단 노드가 다음 노드를 가리키지 않도록 한다
                if otherHead is None:
                    otherHead = head
                    head.next = None
                # 탐색 중이면 이전 노드를 가리키도록 한다
                else:
                    head.next = otherHead
                    otherHead = head

                return self.__reverseListRecusively( newHead, otherHead )