[LeetCode] 206. 역순 연결 리스트(Reverse Linked List)

연결 리스트를 뒤집어라.

 

ex)

 

Input: head = [1,2,3,4,5]

Output: [5,4,3,2,1]

 

 

 

 

 

** 깔끔 답안 **

 

 

 

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: ListNode) -> ListNode:
        def reverse(node, prev = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
 
        return reverse(head)

 

해설:

 

(아 재귀 함수 ㅈ같다...)

함수가 재귀적으로 반복되려면

함수의 인자로 조금씩 범위가 좁아지는 node와

점점 역순이 생겨나는 prev가 들어가야 한다.

 

예를 들어 input을 위 ex의 값이라 하자.

 

next라는 변수를 하나 만들어서 node의 next부터를 저장시키고

node의 next를 prev로 지정하면 

next : 2->3->4->5

node : 1

이 된다.

 

재귀를 거치고 다음은

next : 3->4->5

node : 2->1

이 된다.

 

조금씩 next의 범위가 줄어들고 node의 범위가 늘어나는 게 보이는가?

이 짓을 존나 반복하면 나중에는

next : None

node : 5->4->3->2->1

이 된다.

 

 

 

 

 

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: ListNode) -> ListNode:
        node, prev = head, None
 
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
 
        return prev

 

해설:

 

일부러 재귀 코드와 비슷하도록 

head가 node가 되도록 맞춰봤다.

전반적인 코드는 재귀랑 비슷해서 이해하기 수월할 것이다.

 

개인적으로 재귀보다 이 코드가 더 나은 것 같다.

왜냐하면 재귀를 제대로 쓸 줄 몰라서..ㅎ

 

 

 

****************** 재귀 함수 이해에 좋은 영상 ******************

https://youtu.be/aPYE0anPZqI