Reverse a Linked List

문제 링크

• https://leetcode.com/problems/reverse-linked-list/

문제 설명

단일 연결 리스트의 head가 주어졌을 때, 이 리스트를 뒤집어서 반환하는 함수를 작성하세요.

• 입력: 연결 리스트의 head (노드의 값으로 이루어진 단일 연결 리스트)
• 출력: 뒤집힌 연결 리스트의 head

예제

• 예제 1
  • 입력: head = [1,2,3,4,5]
  • 출력: [5,4,3,2,1]
• 예제 2
  • 입력: head = [1,2]
  • 출력: [2,1]
• 예제 3
  • 입력: head = []
  • 출력: []

풀이 전략

연결 리스트를 뒤집기 위해서는 현재 노드와 이전 노드를 추적하면서, 현재 노드의 next 포인터를 이전 노드를 가리키도록 변경하는 방법을 사용할 수 있습니다.

1. 반복문을 통한 뒤집기:
   • current 포인터를 head로 초기화하고, previous 포인터를 None으로 설정합니다.
   • 각 노드에 대해 next 포인터를 임시 변수에 저장하고, current.next를 previous로 설정하여 현재 노드의 방향을 뒤집습니다.
   • previous를 현재 노드로 이동하고, current를 다음 노드로 이동합니다.
   • current가 None이 되면 previous가 새롭게 뒤집힌 리스트의 head가 됩니다.
2. 재귀를 통한 뒤집기:
   • 연결 리스트의 끝까지 재귀적으로 탐색한 후, 반환되는 노드부터 역순으로 next 포인터를 설정하여 연결을 뒤집습니다.
   • 재귀를 사용할 경우 공간 복잡도가 높아지지만 코드를 간결하게 작성할 수 있습니다.

코드 분석

방법 1: 반복문을 이용한 연결 리스트 뒤집기

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        previous = None
        current = head

        while current is not None:
            next_node = current.next  # 다음 노드를 임시 저장
            current.next = previous   # 현재 노드의 방향을 뒤집음
            previous = current        # previous 포인터 이동
            current = next_node       # current 포인터 이동

        return previous

• 동작 원리:
  • previous 포인터는 현재 노드의 이전 노드를 가리키고, current는 현재 노드를 가리킵니다.
  • next_node에 현재 노드의 다음 노드를 저장하여 이후 순회를 위해 유지합니다.
  • current.next를 previous로 설정하여 연결 방향을 뒤집고, previous와 current를 각각 한 칸씩 앞으로 이동시킵니다.
  • current가 None이 되면 리스트가 모두 뒤집힌 상태이며, previous가 뒤집힌 리스트의 새 head가 됩니다.
• 시간 복잡도: (O(n)) - 리스트의 모든 노드를 한 번씩 방문합니다.
• 공간 복잡도: (O(1)) - 추가 메모리를 거의 사용하지 않습니다.

방법 2: 재귀를 이용한 연결 리스트 뒤집기

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        reversed_head = self.reverseList(head.next)  # 뒤집힌 하위 리스트의 head

        head.next.next = head  # 다음 노드의 next를 현재 노드로 연결
        head.next = None       # 현재 노드의 next를 None으로 설정 (새 마지막 노드가 됨)

        return reversed_head

• 동작 원리:
  • 리스트 끝까지 재귀 호출로 들어간 후, 반환된 노드부터 역방향으로 next 포인터를 조정합니다.
  • head.next.next = head를 통해 다음 노드의 방향을 현재 노드로 뒤집고, head.next = None으로 마지막 노드가 되도록 설정합니다.
  • reversed_head는 새롭게 뒤집힌 리스트의 head가 됩니다.
• 시간 복잡도: (O(n)) - 리스트의 모든 노드를 한 번씩 방문합니다.
• 공간 복잡도: (O(n)) - 재귀 호출 스택의 깊이만큼 공간을 사용합니다.

요약

• 연결 리스트를 뒤집기 위해 반복문과 재귀 두 가지 방법을 사용할 수 있습니다.
• 반복문은 시간 복잡도 (O(n)), 공간 복잡도 (O(1))로 효율적입니다.
• 재귀는 시간 복잡도 (O(n)), 공간 복잡도 (O(n))이며, 코드가 간결해지지만 스택 공간을 추가로 사용하게 됩니다.