Given a sorted linked list, delete all duplicates such that each element appear only once.
For example,
Given
Given
Given
1->1->2
, return 1->2
.Given
1->1->2->3->3
, return 1->2->3
.
Solution:
Two pointers:
Check if the current.value==pre.value, if yes, skip the current node, and set current.next as the current. if no, link it to the pre.next which will delete all the duplicates between these two nodes and proceed the current.
Tips: don't forget to set pre.next=null, when the loop finished. Eg. 1->1->1; if we don't set the pre.next=null, it won't delete the last duplicate nodes.
Time complexity: O(n)
public ListNode deleteDuplicates(ListNode head) {
if(head==null || head.next==null) return head;
ListNode cur=head.next;
ListNode pre=head;
while(cur!=null){
if(cur.val!=pre.val){
pre.next=cur;
pre=cur;
}
cur=cur.next;
}
pre.next=null;
return head;
}
No comments:
Post a Comment