CS 공부 & 면접 대비 0x03 [자료구조] :연결 리스트에서 중간값을 찾는 효율적인 방법

연결 리스트에서 중간값을 찾는 효율적인 방법: 두 포인터 활용

---

질문

연결 리스트에서 한 번에 중간값을 찾는 방법은 무엇인가요?

---

답변

연결 리스트에서 중간값을 찾으려면 두 개의 포인터를 사용하는 방법이 가장 효율적입니다.

• 하나의 포인터는 한 칸씩 이동하고, 다른 하나는 두 칸씩 이동합니다.
• 두 칸씩 이동하는 포인터가 리스트의 끝에 도달했을 때, 한 칸씩 이동하는 포인터가 가리키는 노드가 중간값을 갖는 노드입니다.

이 방법은 O(n) 시간 복잡도로 연결 리스트의 중간값을 찾을 수 있습니다.

---

질문과 답변에 대한 설명

1. 연결 리스트에서 중간값을 찾는 문제란?

연결 리스트는 배열과 달리 **인덱스로 임의 접근(Random Access)**이 불가능합니다. 따라서, 중간값을 찾으려면 순차적으로 노드를 탐색해야 합니다.
기본적으로, 중간값을 찾으려면 두 가지 방법이 있습니다:

1. 전체 길이를 구한 뒤 다시 중간값을 계산 (두 번 순회 필요).
2. 두 개의 포인터를 사용하여 한 번의 순회로 중간값을 찾는 방법.

두 번째 방법이 더 효율적이며, 면접에서도 자주 사용됩니다.

---

2. 두 포인터를 활용한 방법

이 방법에서는 두 개의 포인터를 사용합니다:

• 느린 포인터(slow): 한 번에 한 칸씩 이동합니다.
• 빠른 포인터(fast): 한 번에 두 칸씩 이동합니다.

작동 방식:

1. 두 포인터를 연결 리스트의 **헤드(head)**에 위치시킵니다.
2. **빠른 포인터(fast)**가 연결 리스트의 끝에 도달할 때까지, 두 포인터를 이동시킵니다:
   • 느린 포인터는 한 칸씩 이동.
   • 빠른 포인터는 두 칸씩 이동.
3. 빠른 포인터가 끝에 도달하면, 느린 포인터가 가리키는 노드가 중간값입니다.

---

3. Python 코드 예시

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def find_middle(self):
        slow = self.head
        fast = self.head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        return slow.data

# 연결 리스트 생성 및 중간값 찾기
ll = LinkedList()
ll.add(5)
ll.add(4)
ll.add(3)
ll.add(2)
ll.add(1)

print("중간값:", ll.find_middle())  # Output: 중간값: 3

 

---

4. 이 방법의 시간 및 공간 복잡도

• 시간 복잡도: O(n)
  연결 리스트를 한 번만 순회하므로 효율적입니다.
• 공간 복잡도: O(1)
  두 개의 포인터만 추가로 사용하므로 공간 효율적입니다.

---

응용: 홀수/짝수 길이의 연결 리스트 처리

이 알고리즘은 홀수 길이의 리스트에서도 정확히 중간값을 찾을 수 있습니다.
짝수 길이의 리스트에서는 느린 포인터가 중간에 가까운 두 값 중 두 번째 값을 반환합니다.

---

결론

연결 리스트에서 중간값을 찾는 문제는 효율적인 알고리즘 설계를 배우기에 좋은 사례입니다.

• 이 방법은 단순하면서도 최적의 성능을 제공합니다.
• 두 포인터를 사용하는 접근법은 연결 리스트뿐만 아니라, 다양한 문제(예: 사이클 감지, 교차점 찾기)에도 활용 가능합니다.