연결리스트 투 포인터(런너) 기법, Reverse Linked List

1. 투 포인터 기법

1) 개요

• 두 개의 포인터(slow, fast)를 이용하여 연결 리스트의 사이클을 탐지하는 방법
• slow 포인터는 한 번에 1칸씩 이동하고, fast포인터는 한 번에 2칸씩 이동

 

 

2) 사이클이 없는 경우

• 만약 연결 리스트에 사이클이 없는 경우, fast포인터는 리스트의 끝(None)에 도달함
• 예를 들어, A -> B -> C -> D -> None의 리스트에서, fast 포인터는 한 번에 두 칸씩 이동하면서 끝에 도달함
  • slow 포인터: A -> B -> C -> D
  • fast 포인터: A -> C -> None

 

 

3) 사이클이 있는 경우

• 사이클이 있을 경우, fast 포인터가 slow포인터를 따라잡고 만나게 되는 지점이 생김
• 마치 원이 있는 트랙에서 두 사람이 달릴 때, 빠르게 달리는 사람이 결국 느리게 달리는 사람을 한 바퀴 돌고 따라잡는 것과 같은 원리

 

 

4) 시간 및 공간 복잡도

시간 복잡도

1. 사이클이 없는 경우
   • fast 포인터는 두 칸씩 이동하고, slow 포인터는 한 칸씩 이동
   • 리스트의 길이가 N이라면, fast 포인터가 리스트의 끝(null)에 도달하는 데 N/2번 이동
   • 결과적으로, 전체 루프를 최대 N번 수행하게 되므로, 시간 복잡도는 $O(N)$
2. 사이클이 있는 경우
   • 두 포인터가 리스트의 사이클에서 만나게 되는 시점까지 걸리는 시간도 생각해야 함
   • fast 포인터는 매번 slow 포인터보다 한 칸씩 더 이동하므로, 사이클의 길이가 M이라면, M번 이동하면 두 포인터가 만날 수 있음
   • 사이클의 길이 M은 리스트의 전체 길이 N보다 작거나 같으므로 (M <= N), 전체 루프가 최대 N번만 수행됨
   • 따라서, 사이클이 있는 경우에도 시간 복잡도는 $O(N)$

 

공간 복잡도

• 포인터 두 개(slow, fast)는 고정된 크기의 메모리 공간만 차지하므로, 리스트의 크기(n)에 상관없이 일정한 공간만 사용함
• 따라서, 공간 복잡도는 $O(1)$

 

 

 

2. Reverse Linked List

1) 개요

• 단일 연결 리스트가 주어졌을 때, 노드의 순서를 반대로 바꾸는 것
  • 원래 리스트: 23 -> 6 -> 15 -> NULL
  • 뒤집힌 리스트: 15 -> 6 -> 23 -> NULL
• 기존 리스트의 노드를 순서대로 반복하면서, 각 노드를 새로운 리스트의 앞에(head)에 추가하는 방식으로 연결 리스트를 뒤집음

 

 

2) 예시

1. 초기상태

• 23이 현재의 head 노드

2. 첫번째 단계

• 현재 head 노드의 다음 노드(6)를 가져와, 새로운 리스트의 앞(head)에 추가

3. 두번째 단계

• 현재 head 노드의 다음 노드(15)를 가져와, 새로운 리스트의 앞(head)에 추가

4. 종료

• 현재 head 노드의 다음 노드가 NULL이라면, 리스트의 끝에 도달한 것이기 때문에, 반복을 종료하고 새로운 head를 반환

 

 

3) Reverse Linked List 구현(Leetcode 예제)

문제

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

 

구현

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

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