Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.
Method:
Create a dummy node as a prev node. If current node == next node, then we can't use current node because it's duplicate. so we set prev.next = null, and keep traversing linked list until we find a different value. If current node != next node, then we can use current node, so we set prev.next = curr, and update curr to be next. Return dummy.next as new head
Solution:
Time: O(n) Space: O(1)
/** * Definition for singly-linked list. * class ListNode { * public int val; * public ListNode next; * ListNode(int x) { val = x; next = null; } * } */ public class Solution { public ListNode deleteDuplicates(ListNode A) { ListNode dummy = new ListNode(Integer.MAX_VALUE); ListNode prev = dummy; prev.next = A; ListNode curr = A; ListNode next = A.next; while (curr != null && next != null) { if (curr.val != next.val) { prev.next = curr; prev = curr; curr = next; next = next.next; } else { prev.next = null; while (curr != null && curr.val == next.val) { curr = curr.next; } if (curr != null) { next = curr.next; } } } return dummy.next; } }