206. Reverse Linked List

---

Problem

Reverse a singly linked list.

Example

Solution

---

prev 변수를 이용한 스왑하는 반복방법으로 풀이

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        while head:
            cur = head
            head = head.next
            cur.next = prev
            prev = cur
        return prev

Runtime : 32 ms

• 이해를 돕기위한 시각적 자료
  

https://www.geeksforgeeks.org/reverse-a-linked-list/ 참조

재귀 구조를 이용한 풀이

class Solution:
    def reverseList(self, head: ListNode) -> 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)

Runtime : 36 ms

• 방식은 위와 비슷하나 이번 풀이는 재귀함수를 이용하여 풀이

두 풀이 방법다 성능이 비슷하지만 반복이 재귀에 비해 70% 수준의 메모리를 차지해 공간 복잡도가 더 낮으며, 실행 시간 또한 약간더 빠르다