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.
Analyis:
The problem itself is not a big deal. At first shot, I used a HashSet to save nodes. Code is as follows
However it turns out to be wrong because of the misunderstanding of HashSet. contains() which calls equals() to compare. It works for primitive type. See the accepted code.
Actually it also works for String type. Here is the explanation from Oracle Documentation.
To test whether two objects are equal in the sense of equivalency (containing the same information), you must override the
Consider this code that tests two instances of the 
This program displays 
You should always override the
Solution II
The list is sorted, so simply compare current node with previous node. Code:
The equals() Method
Theequals() method compares two objects for equality and 
returns true if they are equal. The equals() method 
provided in the Object class uses the identity operator 
(==) to determine whether two objects are equal. For primitive data 
types, this gives the correct result. For objects, however, it does not. The 
equals() method provided by Object tests whether the 
object references are equal—that is, if the objects compared are the 
exact same object.To test whether two objects are equal in the sense of equivalency (containing the same information), you must override the
equals() 
method. Here is an example of a Book class that overrides 
equals():public class Book {
    ...
    public boolean equals(Object obj) {
        if (obj instanceof Book)
            return ISBN.equals((Book)obj.getISBN()); 
        else
            return false;
    }
}
Book class 
for equality:// Swing Tutorial, 2nd edition
Book firstBook  = new Book("0201914670");
Book secondBook = new Book("0201914670");
if (firstBook.equals(secondBook)) {
    System.out.println("objects are equal");
} else {
    System.out.println("objects are not equal");
}
objects are equal even though 
firstBook and secondBook reference two distinct 
objects. They are considered equal because the objects compared contain the same 
ISBN number.You should always override the
equals() method if the identity 
operator is not appropriate for your class.Solution II
The list is sorted, so simply compare current node with previous node. Code:
Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given
Given
Given
1->2->3->3->4->4->5, return 1->2->5.Given
1->1->1->2->3, return 2->3.
I solved this problem with two HashSet by extending the first problem. Delete in place is possible, but is kinda complicated. 
No comments:
Post a Comment