82. Remove Duplicates from Sorted List II

MAKGA 2021. 8. 29. 10:55

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

Remove Duplicates from Sorted List II - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

Node의 리스트가 주어졌을 때, 중복된 값을 가진 Node들을 모두 제거해 반환하는 문제다.

Input: 1, 2, 2, 3, 4, 5, 5, 5

Ouput: 1, 3, 4

현재 Node와 이전 Node, 다음 Node 3가지를 전부 비교해서 다른 경우에만 목록에 추가해가며 완성하면 된다.

/**
* 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* new_list = new ListNode(-101);
  ListNode* prev = new_list;
  ListNode* ret = new_list;

  while (head)
  {
  if (head->val != prev->val
  && (!head->next || head->val != head->next->val))
  {
  new_list->next = head;
  new_list = new_list->next;
  }

  prev = head;
  head = head->next;
  }

  new_list->next = nullptr;
  return ret->next;
  }
};