83. 정렬된 리스트에서 중복 제거

이 문제는 정렬된 연결 리스트에서 중복된 값을 제거하여 각 요소가 한 번씩만 나타나도록 하는 것입니다. 주어진 연결 리스트는 이미 정렬되어 있기 때문에, 중복된 값들은 서로 인접해 있다는 점을 활용할 수 있습니다. 이제 주어진 코드를 통해 문제를 해결하는 방법을 단계별로 설명하겠습니다.

1. 알고리즘의 핵심 아이디어

정렬된 연결 리스트에서 중복된 요소들은 서로 인접해 있습니다. 따라서 리스트를 순회하면서 현재 노드의 값과 다음 노드의 값을 비교하여, 중복된 경우 다음 노드를 건너뛰는 방식으로 중복을 제거할 수 있습니다.

2. 코드의 주요 로직 설명

주어진 함수 deleteDuplicates는 연결 리스트의 머리 노드 head를 입력으로 받아 중복을 제거한 후의 리스트를 반환합니다. 이 함수는 다음과 같은 주요 단계를 포함합니다:

1. current라는 포인터를 사용하여 리스트를 순회합니다. 이 포인터는 현재 노드를 가리킵니다.
2. current와 current.next가 모두 존재하는 동안 반복문을 실행합니다.
3. 현재 노드의 값(current.val)과 다음 노드의 값(current.next.val)을 비교합니다.
   • 두 값이 같다면, 중복이므로 current.next를 current.next.next로 설정하여 다음 노드를 건너뜁니다.
   • 두 값이 다르다면, 중복이 아니므로 current를 다음 노드로 이동합니다.
4. 모든 노드를 순회한 후, 중복이 제거된 리스트의 머리 노드 head를 반환합니다.

3. 각 단계별 동작 과정

• 초기화: current를 head로 설정합니다.
• 반복문 실행: current와 current.next가 존재하는 동안 반복합니다.
  • 중복 확인: current.val과 current.next.val이 같으면, current.next를 current.next.next로 설정하여 중복 노드를 제거합니다.
  • 중복이 아닐 경우: current를 current.next로 이동하여 다음 노드로 진행합니다.
• 반복 종료: 리스트의 끝에 도달하면 반복문이 종료되고, 중복이 제거된 리스트의 머리 노드인 head를 반환합니다.

4. 핵심 변수들의 역할

• current: 현재 탐색 중인 노드를 가리키는 포인터입니다. 리스트를 순회하면서 중복을 확인하고 제거하는 역할을 합니다.
• current.next: 현재 노드의 다음 노드를 가리킵니다. 중복 여부를 확인하기 위해 사용됩니다.

5. 왜 이 방법이 효과적인지

이 방법은 리스트가 이미 정렬되어 있다는 점을 활용하여, 인접한 노드들만 비교함으로써 중복을 효율적으로 제거합니다. 이로 인해 추가적인 데이터 구조나 복잡한 연산 없이 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 이는 리스트의 길이에 비례하는 시간만 소요되므로 매우 효율적입니다.

이와 같은 방법으로 정렬된 연결 리스트에서 중복을 제거할 수 있으며, 코드의 간결함과 효율성 덕분에 매우 효과적인 해결책이 됩니다.