Given a singly linked list, remove all the nodes which have a greater value on right side.
Examples:
a) The list 12->15->10->11->5->6->2->3->NULL should be changed to 15->11->6->3->NULL. Note that 12, 10, 5 and 2 have been deleted because there is a greater value on the right side.
When we examine 12, we see that after 12 there is one node with value greater than 12 (i.e. 15), so we delete 12. When we examine 15, we find no node after 15 that has value greater than 15 so we keep this node. When we go like this, we get 15->6->3
b) The list 10->20->30->40->50->60->NULL should be changed to 60->NULL. Note that 10, 20, 30, 40 and 50 have been deleted because they all have a greater value on the right side.
c) The list 60->50->40->30->20->10->NULL should not be changed.
This question is attributed to GeeksForGeeks.
Looking for code-review, optimizations and best practices
public class DeleteGreaterValueOnLeft {
private Node first;
private Node last;
private int size;
public DeleteGreaterValueOnLeft(List<Integer> items) {
for (Integer item : items) {
add (item);
}
}
private void add (Integer item) {
Node node = new Node(item);
if (first == null) {
first = last = node;
} else {
last.next = node;
last = node;
}
size++;
}
public static class Node {
private Node next;
private int item;
Node (int item) {
this.item = item;
}
}
public void deleteCurrentIfNextGreater() {
reverse();
delete();
reverse();
}
private void reverse() {
Node prev = null;
Node ptr = first;
Node ptrNext = null;
while (ptr != null) {
ptrNext = ptr.next;
ptr.next = prev;
prev = ptr;
ptr = ptrNext;
}
first = prev;
}
private void delete () {
Node ptr = first;
while (ptr.next != null ) {
if (ptr.item > ptr.next.item) {
ptr.next = ptr.next.next;
} else {
ptr = ptr.next;
}
}
}
// size of new linkedlist is unknown to us, in such a case simply return the list rather than an array.
public List<Integer> toList() {
List<Integer> list = new ArrayList<>();
if (first == null) return list;
for (Node x = first; x != null; x = x.next) {
list.add(x.item);
}
return list;
}
@Override
public int hashCode() {
int hashCode = 1;
for (Node x = first; x != null; x = x.next)
hashCode = 31*hashCode + (x == null ? 0 : x.hashCode());
return hashCode;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
DeleteGreaterValueOnLeft other = (DeleteGreaterValueOnLeft) obj;
Node currentListNode = first;
Node otherListNode = other.first;
while (currentListNode != null && otherListNode != null) {
if (currentListNode.item != otherListNode.item) return false;
currentListNode = currentListNode.next;
otherListNode = otherListNode.next;
}
return currentListNode == null && otherListNode == null;
}
}
public class DeleteGreaterValueOnLeftTest {
@Test
public void test1() {
DeleteGreaterValueOnLeft dgvol1 = new DeleteGreaterValueOnLeft(Arrays.asList(1, 2, 3, 4, 5));
dgvol1.deleteCurrentIfNextGreater();
assertEquals(new DeleteGreaterValueOnLeft(Arrays.asList(5)), dgvol1);
}
@Test
public void test2() {
DeleteGreaterValueOnLeft dgvol2 = new DeleteGreaterValueOnLeft(Arrays.asList(5, 4, 3, 2, 1));
dgvol2.deleteCurrentIfNextGreater();
assertEquals(new DeleteGreaterValueOnLeft(Arrays.asList(5, 4, 3, 2, 1)), dgvol2);
}
}
