Problem
정렬된 Linked List에서 중복된 값을 제거하는 문제이다. 그러나 LeetCode03 문제와는 다르게 중복된 모든 값들을 남기지 않고 삭제해야한다.
Solution
Leetcode03 문제의 Solution과는 다르게 중복이 시작되는 지점부터 노드를 삭제해한다는 점을 기억하자.
1) current.next.val와 current.next.next.val의 비교
여기서 주의할 점은, current.next와 current.next.next를 비교하게 되면 맨 시작점인 head와 head.next의 값은 비교되는 시점이 없다는 것이다.
이를 위해 current의 값이 head일 때 head와 head.next의 값을 비교하는 코드를 추가하였다.
만약 head와 head.next의 값이 동일하다면, 해당 value를 저장해둔뒤 같은 value가 나타나지 않을 때까지 head를 삭제해주면 된다.
예를 들어, 1->1->1->2->3이면 1이 없어질 때 까지 head를 3번 삭제해줘야 한다.
head를 삭제할 때는 head를 한 칸씩 이동해주는 방식으로 쉽게 구현 가능하다.
current = head
dupnum = None
while (current != None and current.next != None ):
if (current == head and current.val == current.next.val):
dupnum = current.val
while (head != None and head.val == dupnum):
head = head.next
current = head
else:
if (current.next.next != None and current.next.val == current.next.next.val):
dupnum = current.next.val
while (current.next != None and current.next.val == dupnum):
current.next = current.next.next
else:
current = current.next
return head이 방식을 통해 문제를 풀면 current가 head일때와 아닐때의 조건문을 추가해줘야한다는 점이 번거로웠는데, 쉽게 해결할 수 있는 방안을 찾았다.
2) 첫 시작노드가 None인 주어진 리스트를 복제한 새로운 리스트 생성 (e.g., None->1->1->1->2->3)
그러면 시작 지점부터 current.next와 current.next.next값을 비교하더라도 기존 head의 값을 포함하여 비교가능하다.
이렇게 풀게 되면 하나의 비교문으로 간단히 문제를 해결할 수 있다.
duplist = ListNode(None)
duplist.next = head
l = duplist
dupnum = None
while (l.next != None and l.next.next != None):
if (l.next.val == l.next.next.val):
dupnum = l.next.val
while (l.next != None and l.next.val == dupnum):
print(l.next.val)
l.next = l.next.next
else:
l = l.next
return duplist.next