[LeetCode 해석 및 풀이] 206. Reverse Linked List

LeetCode 문제 해석 및 풀이 방법
 

문제 206. Reverse Linked List(연결 리스트 역전)

바로가기
 

문제 설명

영문

Given the head of a singly linked list, reverse the list, and return the reversed list.
 

한글

단일 연결 리스트의 head가 주어지면, 리스트를 역전하고 역전된 리스트를 반환하십시
 

제한조건

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

입출력 예

입력	출력
[1,2,3,4,5]	[5,4,3,2,1]
[1,2]	[2,1]
[]	[]

 
 

해답 및 해설

파이썬 (Python)

순회를 이용하는 방법

# 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]:
        now_node = head
        prev_node = None
        next_node = None

        while not now_node is None:
            next_node = now_node.next
            now_node.next = prev_node
            prev_node = now_node
            now_node = next_node
        
        return prev_node

리스트를 하나씩 순회하며 방향을 바꾸는 방법
 

재귀를 이용한 방법

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        else:
            new_head = head
            if head.next:
                new_head = self.reverseList(head.next)
                head.next.next = head
            head.next = None
            
            return new_head

재귀로 역전된 리스트를 불러와주는 방법