206. 역순 연결 리스트

206. Reverse Linked List
Easy
파이썬 알고리즘 인터뷰 219p

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

♬idea

• iteratively
• recursively

1. iteratively

# 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]:
        node, prev = head, None
        
        # while 반복문 작성
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
            
        return prev

 

2. recursively

# 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]:

		# 재귀적으로 호출할 함수 작성
        def reverse(node: ListNode, prev: ListNode = None):
            if not node:
                return prev
            next, node.next = node.next, prev
            return reverse(next, node)
        
        return reverse(head)