[Leetcode] 82. Remove Duplicates from Sorted List II

문제 : https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/

---

정렬된 linked list의 head 노드가 주어지면 중복된 번호를 가진 노드들은 모두 삭제하고 고유한 번호를 가진 노드들만 남겨라.

---

head 노드의 앞에서부터 탐색하며 탐색중인 노드의 next 노드가 없거나 탐색중인 노드의 val 와 next 노드의 val이 다른경우 고유한 노드가 된다.

이 경우 탐색중인 노드는 삭제하지 않고 남겨야 하므로 별도의 ListNode 포인터 변수(let, prev)에 저장해둔다. prev->next에 현재 노드를 연결시켜준 뒤 prev도 탐색중인 노드로 갱신한다.

그리고 최초로 찾은 고유한 노드는 새로운 head 노드가 되므로 이를 또 다른 변수에 저장해둔다. 나중에 탐색이 끝난 후 해당 node를 반환해줘야한다.

만일 탐색중인 노드의 next 노드의 val과 탐색중인 노드의 val 이 동일하다면 삭제되어야하므로 next 노드를 계속 탐색하며 val 과 동일한 node들은 저장하지 않고 패스한다.

 

시간복잡도는 O(N). N = |linked list|

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/82.%20Remove%20Duplicates%20from%20Sorted%20List%20II.cpp