[리트코드] Remove Duplicates(중복 제거)

Leetcode Question 82 and 83 is all about working with duplicates.

In this case we want to kill a bird with one stone. How we would achieve that is by first seeing how we
solved the question 82

82. Remove Duplicates from Sorted List II

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.

Using two pointers

In the pointers, we would use a dummyNode that serves as a pointer to hold
our result.and it points to the head.
The previous node holds the dummy head and the current node
points to the head.

    ListNode dummyNode = new ListNode();
    dummyNode.next = head;

    ListNode prev = dummyNode, cur = head;

Goal of Operation

Our goal is to move the current node and to eliminate all duplicate
values we meet. This implies the current node value should not be
same as the next node value.
If the current node value is same as the next nodes value we have
to keep moving current until we find node who's value is not same
as the current node.

[1,2,3,3,4,4,5]
if we started from 2-- we need to move to 3-3-4
and prev is 4.
from 4->4->5
Now we remove 4.But skipping its values

Skipping duplicates and making sure we dont add duplicates to the results.(prev that points to our dummy
node).

   if (cur.next != null && cur.val == cur.next.val) {
        while (cur.next != null && cur.val == cur.next.val) cur = cur.next;
        prev.next=cur.next;
      }

else if next is not duplicate then we just keep it in the prev(dummy updator).

else {
        prev = cur;
      }

End result

What we need to return is the dummy nodes next.
remember the dummy nodes next value is the prev(root).
And we used the prev to do our operation.

Final Code

 public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }

    ListNode dummyNode = new ListNode();
    dummyNode.next = head;

    ListNode prev = dummyNode, cur = head;

    while (cur != null) {
      if (cur.next != null && cur.val == cur.next.val) {
        while (cur.next != null && cur.val == cur.next.val) cur = cur.next;
        prev.next=cur.next;
      } else {
        prev = cur;
      }
      cur=cur.next;
    }

    return dummyNode.next;
  }

Kill two Birds with one Stone.

In this question we were just removing all duplicates. But in
leetcode 83 we just wanted to hold only unique values.
little modification to our code gives a passing solution
to that problem.

83. Remove Duplicates from Sorted List

We just element the changes in iterating to find all duplicates skipped in the while loop.

 class Solution {
  public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null)return head;


    ListNode dummyNode = new ListNode();
    dummyNode.next = head;

    ListNode prev = dummyNode, cur = head;

    while (cur != null) {
      if (cur.next != null && cur.val == cur.next.val) {
        // while (cur.next != null && cur.val == cur.next.val)cur = cur.next;

        prev.next=cur.next;
      } else {
        prev = cur;
      }
      cur=cur.next;
    }

    return dummyNode.next;
  }
}

Summary

Usually better to make little modification to do some jobs.
Even though it might not be the efficient way. Optimize later if needed