a) { IntNode pos = head; while (pos != null && pos.next != null) { pos.next = po

Question

a) {
IntNode pos = head;
while (pos != null && pos.next != null)
{
pos.next = pos.next.next;
pos = pos.next;
}
}

b)
int countDuplicates(IntNode head)
{
int numduplicates = 0;

for (IntNode current = head ; current != null ; current = current.next)
{
boolean found = false;
IntNode other = current.next;
while ( !found && other != null )
{
if (other.data == current.data)
{
found = true;
}

other = other.next;
}

if (found)
{
numduplicates++;
}
}

return numduplicates;
}
c)
IntNode attachLists(IntNode head1, IntNode head2)
{
IntNode combined = head1;

if (head1 == null) {
combined = head2;
} else {
IntNode pos = head1;
while (pos.next != null)
{
pos = pos.next;
}
pos.next = head2;
}

return combined;
}

d)
int foo(IntNode head)
{
int product = 1;

IntNode pos = head;
while (pos != null)
{
if (pos.data == 0)
{
pos.data = 1;
pos = head;
}
else
{
product = product * pos.data;
pos = pos.next;
}
}

return product;
}

e)
int sumOfPowersOf2(IntNode head)
{
int sum = 0;

for (IntNode pos = head ; pos != null ; pos = pos.next)
{
int product = 1;
for (int i = 0 ; i < pos.data ; i++)
{
product = product * 2;
}

sum = sum + product;
}

return sum;
}


a) I figured the run time is O(n)... but I'm not too sure, as for the other four I'm completely lost.

Explanation / Answer

Hope this helps. Let me know if you have any questions. Please rate. :)

a) O(n) - single loop running through the data once.

b) O(n2) - loop within a loop. The inner loop runs in O(n) time, and that loop will execute once each time the outer loop executes. The outer loop executes O(n) times, so the overall complexity is O(n2).

c) O(n) where n is the size of list1. If list 1 is empty, this is O(1). Otherwise, it runs through all of list 1 to get to the end, and then tacks on list2 to the end in constant time. The run through of list1 is what gives it O(n) time.

d) Every time we encounter a data of 0, we start back at the beginning of the list. In the best case, if no data is 0, we will run through only once, and this would have O(n) time. In the worst case, however, if all the data is 0, we go back to the start once for every new piece of data, so this is O(n2) time. We almost always give upper bounds in terms of worst case runtime, so this runs in O(n2).

e) This one is tricky. The pos.data does not depend on the number if inputs, so we can't put that part in terms of n. If you approximate the inner loop as running in O(1) time (for relatively small powers of 2), then this would run in O(n) time. If you would want to put it in terms of the order of those powers of 2, you could say that this runs in O(n*m) time, where n is the number of elements, and m is the order of the data input. As stated before, for small values of m, this would be O(n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.