Remove Duplicates from Sorted List II[Linked List,Two Pointers]

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

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

 

Example 1:

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

 

Constraints:

• The number of nodes in the list is in the range [0, 300].
• -100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

연습하자 코딩연습!

 

1. C

상처뿐인 영광이다. 너무 안 풀려서 결국엔 GPT를 봤다.

풀릴듯 풀리지 않는 문제였다. 짜증 이빠이..

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(!head || !head->next) return head;

    struct ListNode dummy;
    struct ListNode* slow = &dummy;
    slow->next = head;
    struct ListNode* fast = head;
    while(fast){
        while(fast->next && fast->val == fast->next->val){
            fast = fast -> next;
            }
        if(slow->next == fast){
            slow = slow->next;
        }else{
            slow->next = fast->next;
        }
        fast = fast->next;
    }
    return dummy.next;
}

 

2. C++

근데 희한한건, 내가 꾸역 꾸역 어거지로 만들었다고 생각하는 코드가 결국 정석 코드의 방향이었다는 것이다.

이건 신기하네;;

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode dummy(999,head);
        ListNode* fast = head;
        ListNode* slow = &dummy;

        while(fast){
            while(fast->next && fast->val == fast->next->val){
                fast = fast->next;
            }
            if(slow->next == fast){
                slow = slow->next;
            }else{
                slow->next = fast->next;
            }
            fast = fast->next;
        }

        return dummy.next;
    }
};

 

3. Python

# 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]:
        fast = head
        dummy = ListNode(next=head)
        slow = dummy
        while fast :
            while fast.next and fast.val == fast.next.val :
                fast = fast.next
            if slow.next == fast :
                slow = slow.next
            else :
                slow.next = fast.next
            fast = fast.next

        return dummy.next

 

처음 initialize에 next를 head로 해주는 것이 중요하구나.. 참 쉬운 게 하나 없다.