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