LeetCode 206. Reverse Linked List (Python3)

안녕하세요. 죠쵸입니다.

Leetcode 206번 문제는 난이도 "EASY"에 해당하는 문제로, 문제자체가 기본적으로 간단해서 재귀함수에 익숙하지 않다면, 재귀함수를 연습해보기 좋을 것 같습니다.

leetcode.com/problems/reverse-linked-list

Reverse Linked List - LeetCode

 

#LeetCode 206. Reverse Linked List(Description)

 

LeetCode 206번 문제는 간단합니다. 주어진 Linked List를 Revese 하여 반환하는 것입니다.

 

 

#LeetCode 206. Reverse Linked List(Solution)

 

이번 문제는 재귀함수의 호출을 이용하여 풀이를 진행하였습니다. 재귀함수의 경우는 최종 종료 조건과 반환하는 값을 잘 생각해야 원하는 값을 얻을 수 있습니다. 간단히 풀이과정을 설명하자면, 이전 노드(prev)의 값을 현재 노드(current)의 next에 치환하여 Linked List를 Reverse 처리하게 하였습니다. 아래의 코드를 보시면 이해하실 수 있으리라 생각됩니다. 

 

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

    def _print_all(self):
        while self:
            print(self.val, end=' ')
            self = self.next
        print()

class Solution:
    def reverse(self, current: ListNode, prev: ListNode)-> ListNode:
        if not current:
            return prev

        next = current.next
        current.next = prev
        return self.reverse(next, current)

    def reverseList(self, head: ListNode) -> ListNode:
        return self.reverse(head, None)

 

아래와 같이 위의 풀이를 테스트 해 보았습니다.

solution = Solution()
L1_3 = ListNode(4)
L1_2 = ListNode(2,L1_3)
L1_1 = ListNode(1,L1_2)

print("Before : ", end=" ")
L1_1._print_all()
result = solution.reverseList(L1_1)
print("After : ", end=" ")
result._print_all()

 

LeetCode에 제출된 결과는 아래와 같습니다.

 

방문해 주셔서 감사합니다. 여러분의 공감하기(♥), 댓글과 구독은 저에게 힘이 됩니다.

이상으로 죠쵸였습니다.