LC 206. Reverse Linked List

문제 개요

• Linked List 기본 구현 문제이다.

• Node를 활용한 연결 리스트 개념을 알아야 한다.

• 이 문제에서는 투 포인터를 활용하고 Node의 값과 next 값을 계속 바꿔주기 때문에 코드 순서가 중요하다.

풀이 구상

• Node는 현재 값과, next 값의 주소를 가지고 있다.

• 마지막 노드의 next 값은 None이기 때문에 노드를 하나씩 검사하면서 next 값을 바꿔주고 next가 None일 때 탐색을 종료하면 된다.

• 연결 끊어주고 다음 값으로 이어주는 과정을 구체적으로 살표보자.
  

  • 1의 다음 값이 2인데 1 전에 prev라는 변수에 None을 넣는다.

  • 1의 다음 값을 prev로 변경해서 1, 2 사이의 연결을 끊는다.

  • prev를 current로 할당해준다: prev를 1로 이동 시킴

  • current는 현재 탐색하는 변수로 current의 값을 2로 옮긴다.

  • 위의 과정 반복한다. current의 next 값이 None일 때까지(마지막 값일 때)

문제풀이 코드

# 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]:
        # prev라는 변수 None으로 초기화: current의 next 값을 prev로 바꿔주어 기존 연결을 끊을 예정
        prev, current = None, head

        # current가 None이면 탈출: current == None이면 마지막 값이기 때문
        while current:
            # 일단 current의 next 값을 next_node라는 변수에 할당 해 놓음: current 값을 다음 값으로 옮길 때 필요
            next_node = current.next
            
            # current의 next 값을 prev로 옮김으로써 기존 노드와의 연결을 끊음
            current.next = prev
            
            # prev의 current 값을 넣어줌으로써 prev가 다음 노드로 이동
            prev = current
            
            # current도 다음 노드로 이동
            current = next_node

        return prev

시간복잡도는 한 번만 순회하면 됨: O(n^2)