LeetCode #206 - Reverse Linked List(역순 연결 리스트) 풀이

문제

문제의 내용을 요약하면, 연결 리스트를 역순으로 재구성한 후 반환하여야 한다.

풀이

이 문제는 21. Merge Two Sorted Lists와 같이 새로운 노드를 생성하는 방식으로 해결하는데, 문제에서 주어진 예시로 과정을 나타내보면 다음과 같다.

더미 노드 생성

현재 노드(current)를 연결 리스트의 head로 정하고, 새로운 노드(node를 None으로 초기화한다.

current, node = head, None

반복하며 스와핑

현재 노드 즉, 기존 연결 리스트의 head가 되는 모든 노드를 탐색하며 새로운 노드로 값을 넘겨준다. 이 과정을 다음과 같이 나타낼 수 있다.

첫 번째 반복

current: ListNode: [1 -> 2 -> 3 -> 4 -> 5]

1) next = ListNode: [2 -> 3 -> 4 -> 5]
2) current.next = None
3) node = ListNode: [1]
4) current = ListNode: [2 -> 3 -> 4 -> 5]

두 번째 반복

current: ListNode: [2 -> 3 -> 4 -> 5]

1) next = ListNode: [3 -> 4 -> 5]
2) current.next = ListNode: [1]
3) node = ListNode: [2 -> 1]
4) current = ListNode: [3 -> 4 -> 5]

세 번째 반복

current: ListNode: [3 -> 4 -> 5]

1) next = ListNode: [4 -> 5]
2) current.next = ListNode: [2 -> 1]
3) node = ListNode: [3 -> 2 -> 1]
4) current = ListNode: [4 -> 5]

네 번째 반복

current: ListNode: [4 -> 5]

1) next = ListNode: [5]
2) current.next = ListNode: [3 -> 2 -> 1]
3) node = ListNode: [4 -> 3 -> 2 -> 1]
4) current = ListNode: [5]

다섯 번째 반복

current: ListNode: [5]

1) next = None
2) current.next = ListNode: [4 -> 3 -> 2 -> 1]
3) node = ListNode: [5 -> 4 -> 3 -> 2 -> 1]
4) current = ListNode: None

여섯 번째 반복

current : None

반복 종료

최종 결과 반환

새롭게 구성된 node를 반환한다.

return node

전체 코드

from typing import Optional


# Definition for singly-linked list.
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]:
        current, node = head, None

        while current:
            next = current.next
            current.next = node
            node = current
            current = next

        return