Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
Iterative Solution, O(n) time, O(1) space
1 2 3 4 5 6 7 8 9 10 11 12 13
| public class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode current = head; while (current != null && current.next != null){ if (current.val == current.next.val){ current.next = current.next.next; }else{ current = current.next; } } return head; } }
|
Recursive Solution, O(n) time, O(n) space
1 2 3 4 5 6 7
| public class Solution { public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) return head; head.next = deleteDuplicates(head.next); return head.val == head.next.val ? head.next : head; } }
|