I need help. I need to write a method to determine if a chain of linked nodes is
ID: 3591713 • Letter: I
Question
I need help. I need to write a method to determine if a chain of linked nodes is sorted in ascending order. The method header is:
public boolean isSortedAscending(Node<Comparable> firstInChain)
For full credit, write a solution that is O(n ).
I have driver program where I implemented my method:
public class HomeworkW08Driver
{
public static void main(String[] args)
{
// this code uses the same values as the arrays above
Node<Comparable> sortedChain1 = new Node<Comparable>(2, new Node<Comparable>(5, new Node<Comparable>(7,
new Node<Comparable>(9, new Node<Comparable>(13, new Node<Comparable>(15,
new Node<Comparable>(18)))))));
Node<Comparable> sortedChain2 = new Node<Comparable>(2, new Node<Comparable>(3, new Node<Comparable>(4,
new Node<Comparable>(5, new Node<Comparable>(6, new Node<Comparable>(7,
new Node<Comparable>(8)))))));
Node<Comparable> sortedChain3 = new Node<Comparable>(2, new Node<Comparable>(3, new Node<Comparable>(4,
new Node<Comparable>(5, new Node<Comparable>(6, new Node<Comparable>(7,
new Node<Comparable>(7)))))));
Node<Comparable> sortedChain4 = new Node<Comparable>(2, new Node<Comparable>(2, new Node<Comparable>(2,
new Node<Comparable>(2, new Node<Comparable>(2, new Node<Comparable>(2,
new Node<Comparable>(2)))))));
Node<Comparable> sortedChain5 = null; // empty chain
Node<Comparable> unsortedChain1 = new Node<Comparable>(8, new Node<Comparable>(7, new Node<Comparable>(6,
new Node<Comparable>(5, new Node<Comparable>(4, new Node<Comparable>(3,
new Node<Comparable>(2, new Node<Comparable>(1))))))));
Node<Comparable> unsortedChain2 = new Node<Comparable>(2, new Node<Comparable>(9, new Node<Comparable>(7,
new Node<Comparable>(13, new Node<Comparable>(18, new Node<Comparable>(15,
new Node<Comparable>(4)))))));
Node<Comparable> unsortedChain3 = new Node<Comparable>(2, new Node<Comparable>(3, new Node<Comparable>(4,
new Node<Comparable>(5, new Node<Comparable>(6, new Node<Comparable>(7,
new Node<Comparable>(6)))))));
Node<Comparable> sortedWordChain1 = new Node<Comparable>("apple", new Node<Comparable>("banana",
new Node<Comparable>("carrot", new Node<Comparable>("durian"))));
Node<Comparable> unSortedWordChain1 = new Node<Comparable>("zebra", new Node<Comparable>("hippo",
new Node<Comparable>("gorilla", new Node<Comparable>("elephant"))));
System.out.println(" **********Linked Nodes Method Test");
System.out.println("Sorted numbers 1 sorted? " + isSortedAscending(sortedChain1));
System.out.println("Sorted numbers 2 sorted? " + isSortedAscending(sortedChain2));
System.out.println("Sorted numbers 3 sorted? " + isSortedAscending(sortedChain3));
System.out.println("Sorted numbers 4 sorted? " + isSortedAscending(sortedChain4));
System.out.println("Sorted numbers 5 sorted? " + isSortedAscending(sortedChain5));
System.out.println("Unsorted numbers 1 sorted? " + isSortedAscending(unsortedChain1));
System.out.println("Unsorted numbers 2 sorted? " + isSortedAscending(unsortedChain2));
System.out.println("Unsorted numbers 3 sorted? " + isSortedAscending(unsortedChain3));
System.out.println("Sorted words 1 sorted? " + isSortedAscending(sortedWordChain1));
System.out.println("Unsorted words 1 sorted? " + isSortedAscending(unSortedWordChain1));
}
public static boolean isSortedAscending(Node<Comparable> firstInChain)
{
boolean found = true;
Node<Comparable> currentNode = firstInChain;
while(currentNode!=null && found)
{
if(currentNode.data.compareTo(currentNode.next.data) > 0 )
found = false;
currentNode = currentNode.next;
}
return found;
}
}
But it doesn't work.
I have an error message:
Exception in thread "main" java.lang.NullPointerException
at HomeworkW08Driver.isSortedAscending(HomeworkW08Driver.java:101)
at HomeworkW08Driver.main(HomeworkW08Driver.java:63)
Thanks
Explanation / Answer
Hi, I have fixed the issue.
Please rest now.
public static boolean isSortedAscending(Node<Comparable> firstInChain)
{
// Base case :if firstInChain is null or firstInChain.next is null (one node)
if(firstInChain == null || firstInChain.next == null)
return true;
boolean found = true;
Node<Comparable> currentNode = firstInChain;
while(currentNode.next!=null && found)
{
if(currentNode.data.compareTo(currentNode.next.data) > 0 )
found = false;
currentNode = currentNode.next;
}
return found;
}
}