Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only *distinct* numbers from the original list.

**Example 1:**

Input:1->2->3->3->4->4->5Output:1->2->5

**Example 2:**

Input:1->1->1->2->3Output:2->3

## Solution:

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode cur = head; ListNode dummy = new ListNode(0); ListNode temp = dummy; int prev = 999; while(cur != null && cur.next != null) { if(prev == cur.val || cur.val == cur.next.val) { prev = cur.val; cur = cur.next; } else { ListNode newNode = new ListNode(cur.val); temp.next = newNode; cur = cur.next; temp = temp.next; } } if(cur != null && prev != cur.val) { temp.next = cur; } return dummy.next; } }

Time Complexity: O(n)

Space Complexity: O(n)

## One thought on “5) Remove Duplicates from Sorted List II”