[Leetcode]206. Reverse Linked List

1. 재귀를 이용한 풀이 

  일단, 그렇게 효율적이지는 않다는 생각이 드는 코드다. 왜냐하면, 코드를 짜는 게 어렵기 때문이다. 언젠가는 재귀함수를 정복하겠다.

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]:
        # Base case: if the list is empty or has only one node
        if not head or not head.next:
            return head
        
        # Recursively reverse the rest of the list
        new_head = self.reverseList(head.next)
        
        # Reverse the pointers
        head.next.next = head
        head.next = None
        
        return new_head

 

2. 반복문을 이용한 풀이 

 3개의 pointer를 이용해서 순차적으로 풀어나간다. 상당히 매력적인 코드.

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    	current_node = head 
        after_node = head 
        before_node = None 
        while current_node:
            after_node = after_node.next 
            current_node.next = before_node
            before_node = current_node 
            current_node = after_node 
        return before_node