[LeetCode | Python] 206. Reverse Linked List

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

singly linked list 가 주어지면, reversed list를 반환하는 문제다.

 

 

ListNode 클래스

파이썬에서 연결리스트를 구현하기 위해서는 직접 클래스를 정의해야 한다.

LeetCode 문제에서 제공되는 연결 리스트 정의는 다음과 같다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val    # 현재 노드가 저장하는 값
#         self.next = next  # 다음 노드를 가리키는 포인터

 

 

풀이1: Iteration (반복)

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

prev와 curr 포인터를 이용해 순차적으로 연결을 뒤집음

temp를 이용해 현재 노드의 다음 노드를 미리 저장하여, 포인터 변경 후에도 원래 연결 유지

모든 노드를 순회한 뒤, prev는 역순 리스트의 새로운 헤드가 된다.

 

노드 수만큼 순회하므로 시간복잡도는 O(n),

추가 공간 없이 포인터만 사용하므로 공간 복잡도는 O(1)이다.

 

 

풀이2: Recursion (재귀)

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

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

1. 연결 리스트의 끝까지 재귀적으로 호출하며 이동

2. 리스트의 끝에서부터 현재 노드의 다음 노드를 이용해 연결 방향을 바꿈

3. 재귀 호출이 종료되면서 각 단계에서 새로운 헤드(newHead) 반환

 

노드 수만큼 재귀 호출하므로 시간 복잡도는 O(n)

재귀 호출 스택을 사용하므로 공간 복잡도는 O(n)이다.