[LeetCode] 206. Reverse Linked List

말하는 감자·2024년 12월 2일

algorithm data structure leetcode linked list python 리트코드 알고리즘 연결 리스트 자료구조 재귀 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

18/32

오늘 문제는 링크드 리스트를 이용하는 기본적인 문제입니다. 하지만 구현적으로는 나름 skillful하다고 생각하는 문제입니다.

그럼 살펴보겠습니다!

1. 오늘의 학습 키워드

Linked List
Recursion
구현 잘 하기

2. 문제: 206. Reverse Linked List

단계: Easy
주제: Linked List, Recursion
출처: https://leetcode.com/problems/reverse-linked-list/description/?envType=problem-list-v2&envId=linked-list&difficulty=EASY

Description

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].
5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

3. 문제 풀이

Step1. 문제 이해하기

링크드 리스트 head가 주어졌을때, 이것을 뒤집은 링크드 리스트를 반환하는 문제입니다.

링크드 리스트 내 노드를 순회하면서 노드의 next 방향을 뒤집으면서 진행하면 될 것으로 보입니다. 문제의 입출력을 제약 조건과 함께 보도록 하겠습니다.

Input:
- 링크드 리스트가 주어지는데 이것의 길이는 0이상 5000이하입니다.
  - 링크드 리스트의 길이가 시간 복잡도에 영향을 줄 것으로 보입니다. 길이가 0도 포함된다는 것은 빈 리스트가 들어올수도 있다는것을 의미합니다.
  - 또한, 시간 복잡도는 $O(n^2)$ 까지는 충분할 것으로 보입니다.
- 노드의 값은 -5000이상 5000이하입니다.
Output:
- 뒤집어진 리스트를 반환합니다.

이 내용들을 기반으로 바로 문제를 더 자세하게 분석해보겠습니다.

Step2. 문제 분석하기

주어진 링크드 리스트의 노드를 순회하면서, 현재 노드가 가리키는 방향을 바꾸면 됩니다.

노드를 순차적으로 순회하기 때문에 반복문과 재귀를 사용할 수 있습니다.

두 방법 모두 시간 복잡도가 $O(n)$ 으로 매우 효율적일것으로 예상됩니다.

1. 반복문 접근

핵심 아이디어:
- 각 노드를 순회하면서 현재 노드의 next 포인터를 이전 노드를 가리키도록 뒤집습니다.
- 리스트의 방향성을 바꿔야 하므로 prev(이전 노드), curr(현재 노드), next_node(다음 노드)를 사용하여 포인터를 조작합니다.
필요한 변수:
1. prev: 결과 리스트의 마지막 노드를 가리킵니다. 초기값은 None으로 설정합니다.
2. curr: 현재 작업 중인 노드입니다. 초기값은 입력받은 head입니다.
3. next_node: curr의 다음 노드를 임시 저장하여 포인터를 잃지 않도록 합니다.

2. 재귀 접근

핵심 아이디어:
- 재귀적으로 노드의 next 포인터를 뒤집습니다.
- 기본적으로 재귀 호출을 통해 리스트 끝까지 도달한 뒤, 각 노드의 next 포인터를 역방향으로 설정합니다.
- 마지막 노드가 새 head가 됩니다.
재귀 함수 설계:
- 종료 조건: node가 None이면, 현재 prev를 반환합니다.
- 재귀 호출: 현재 노드의 다음 노드와 이전 노드 정보를 넘겨 다음 호출로 이동합니다.
재귀 호출의 특성상, 스택 프레임에 따라 각 호출이 되돌아오면서 포인터가 역방향으로 설정됩니다.

바로 코드 설계를 진행해보도록 하겠습니다.

Step3. 코드 설계하기

반복문 방법

초기화:
- prev = None: 이전 노드를 초기화합니다.
- curr = head: 현재 작업할 노드를 초기화합니다.
리스트 순회:
- curr가 None이 아닐 때까지 반복합니다.
- curr.next 포인터를 prev로 변경합니다.
- prev를 curr로 이동하고, curr을 다음 노드로 이동합니다.
결과 반환:
- prev는 뒤집힌 리스트의 새로운 head가 되므로 반환합니다.

재귀 방법

재귀 함수 설계:
- recursive_reversed(prev, node):
  - prev: 현재 노드의 이전 노드.
  - node: 현재 작업 중인 노드.
- 종료 조건: node가 None이면, 현재 prev를 반환합니다.
- 포인터 조작: node.next를 prev로 설정하고, 다음 호출로 이동합니다.
초기 호출:
- recursive_reversed(None, head)를 호출하여 시작합니다.
결과 반환:
- 재귀 함수에서 반환된 prev를 최종 반환합니다.

Step4. 코드 구현하기

반복문 방법

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):

    # 1. iterative
    def reverseList(self, head):
        # https://leetcode.com/problems/reverse-linked-list/submissions/1467929284
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prev = None
        curr = head
        while curr:
            next_node = curr.next  # 현재 노드의 다음 노드를 저장
            curr.next = prev  # 현재 노드의 다음 포인터를 뒤집어서 이전 노드를 가리키게 함
            prev = curr  # 결과 리스트의 헤드를 현재 노드로 업데이트
            curr = next_node  # 다음 노드로 이동
        return prev

코드 설명:

next_node는 현재 노드의 next를 저장하여 순회를 계속 진행합니다.
현재 노드(curr)의 next 포인터를 이전 노드(prev)로 뒤집습니다.
prev와 curr을 업데이트하며 리스트를 순회합니다.
시간 복잡도: $O(n)$
- 리스트를 한 번 순회하므로 $O(n)$ .
공간 복잡도: $O(1)$
- 추가 메모리 사용 없이 포인터만 조작합니다.

결과: https://leetcode.com/problems/reverse-linked-list/submissions/1467929284

재귀 방법

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
# # 2. recursion
    def reverseList(self, head):
        # https://leetcode.com/problems/reverse-linked-list/submissions/1467928535
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        def recursive_reversed(prev, node):
            if node:
                next_node, node.next = node.next, prev  # 다음 노드를 저장하고 포인터 뒤집기
                return recursive_reversed(node, next_node)  # 현재 노드를 prev로, 다음 노드를 node로 진행
            else:
                return prev  # node가 None일 때, 이전 노드(prev)가 새 헤드가 됨
        return recursive_reversed(None, head)

코드 설명:

prev와 node를 인자로 받아, 현재 노드의 포인터를 뒤집은 뒤 다음 호출로 이동합니다.
리스트의 끝까지 도달하면 새로운 head(prev)를 반환합니다.

시간 복잡도: $O(n)$

리스트를 한 번 순회하므로 $O(n)$ .

공간 복잡도: $O(n)$

재귀 호출의 깊이에 따라 스택 프레임이 생성되므로 $O(n)$ 의 추가 공간이 필요합니다.

결과: https://leetcode.com/problems/reverse-linked-list/submissions/1467928535

4. 마무리

이번 문제는 Linked List의 구조와 포인터 조작을 이해하는 데 매우 유용한 기본 문제였습니다. 반복문과 재귀를 활용하여 문제를 해결하며, 각각의 접근 방식에서 장단점을 비교할 수 있었습니다.

주요 학습 내용

Linked List의 특징:
- 노드와 포인터를 활용하여 리스트를 구성하는 구조를 이해했습니다.
- 노드의 next 포인터를 변경하여 리스트를 뒤집는 방법을 학습했습니다.
반복문과 재귀의 차이:
- 반복문은 추가 메모리 사용 없이 효율적으로 리스트를 뒤집을 수 있는 방법입니다.
- 재귀는 직관적이고 간결하게 문제를 해결할 수 있지만, 재귀 호출에 따른 스택 사용으로 추가 메모리가 필요합니다.
시간 및 공간 복잡도 비교:
- 시간 복잡도: 두 방법 모두 리스트를 한 번만 순회하므로 $O(n)$ 입니다.
- 공간 복잡도:
  - 반복문: $O(1)$ 로 추가 메모리가 거의 필요 없습니다.
  - 재귀: $O(n)$ 로 호출 스택의 깊이에 따라 메모리가 추가로 사용됩니다.