LeetCode 83(Remove Duplicates from Sorted List, Python)

1. 문제 링크

• Remove Duplicates from Sorted List - LeetCode

Remove Duplicates from Sorted List - LeetCode

2. 문제 설명

• 오름차순 정렬된 연결 리스트(linked list)가 주어졌을 때 중복되는 항목을 제거한 연결 리스트를 반환하는 문제
• 예시) head = [1,1,2]로 주어지면 [1, 2]를 반환. 단, 평소 list가 아님에 유의.
• 연결 리스트에 대해 처음 접하고 기록해둔 글은 이것 참고 LeetCode 21(Merge Two Sorted Lists, Python) (tistory.com)

3. 처음 풀이

• head2를 생성하고 head가 주어졌을 때 값이 다르면 head2에 이어붙여주고, 값이 같으면(중복) 이어붙이지 않는다.
• 이후 head2, head 모두 한 칸씩 이동을 반복

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        result = ListNode(-101) #주어지는 연결리스트의 val은 -100이상 100이하로 이와 겹치지 않게 설정
        head2 = result

        while head:
            if head.val == head2.val: #값이 중복되면 head를 옮겨 저장하지 않고 그냥 다음 칸으로 이동
                head = head.next
            else:
                head2.next = ListNode(head.val) #값이 다르면 head2의 다음 칸에 head를 옮겨 저장
                head = head.next #head 다음 칸으로 이동
                head2 = head2.next #head2도 다음 칸으로 이동
                
        
        return result.next

4. 다른 풀이

• head2에 옮겨줄 때 ListNode(head.val)로 옮기는 것은 val 정보로만 새로 노드를 만드는 어색한 작업
• head의 노드를 그대로 옮겨주는 것이 자연스럽다. 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            if cur.val == cur.next.val: #현재 값과 다음 값이 같으면 다음 노드를 생략(그 다음 노드로 치환)
                cur.next = cur.next.next
            else: #그렇지 않으면 즉, 값이 중복되지 않으면 다음 노드를 가져오기
                cur = cur.next
        return head

5. 배운 점

• 연결 리스트가 아직은 어색함. 
• 다른 사람들 풀이를 많이 접해봐야겠음.