A question about lists in C# or Java :)

[dan2222]

Homework Statement:

'lst' is a linked list that contains different integers from each other. The number of values in the list is even.
Write a method that takes a list, builds a linked list called 'sumq' in which each value includes two of the largest numbers in the list for the set we have not used so far.
It means that one number should not be used more than once. The action must return the 'sumq' list.
For example, the list: lst = {5, 8, 2, -3, 7, 10, 20, 4}
The list that the method will return is: sumq = {30, 15, 9, -1 }
No need to keep the original list.


My own explanation...
It means that the first value of the list 'sumq' is the sum of the 2 largest numbers in the list 'lst' and so on

Relevant Equations:

-

I could not understand the question, I have really tried to solve it but I could not.
I will appreciate any direction to the solution. Thanks in advance:)

 

[phyzguy]

It means that the first value of the list 'sumq' is the sum of the 2 largest numbers in the list 'lst' and so on

I think you have this right. But notice it says that "one number should not be used more than once". So after taking the sum of the two largest numbers, you remove these numbers from the original list 'lst'. Then you repeat the process until 'lst' is empty.

 

[valenumr]

This is an odd homework question. I suppose the point is to understand linked lists? But no real world application should implement the algorithm in this way. Ideally you would just use vectors, and treat the input as a heap.

 

[Halc]

It can be done with linked lists. It would work like an insert-sort in reverse.
At the core, it's asking you to sort the list and then just combine every pair of entries.

 

[valenumr]

It can be done with linked lists. It would work like an insert-sort in reverse.
At the core, it's asking you to sort the list and then just combine every pair of entries.

Sure, but the algorithm is necessarily O(n^2) with a list. See how it runs with a million or so inputs.

 

[phyzguy]

Sure, but the algorithm is necessarily O(n^2) with a list. See how it runs with a million or so inputs.

I don't think the homework is asking to evaluate the quality of the problem. The OP should just implement the problem as requested.

 

[willem2]

I don't think the homework is asking to evaluate the quality of the problem. The OP should just implement the problem as requested.

I think dumping the list into a vector will be easier, as well as more efficient.

 

[dan2222]

Thank you all for the response!

 

[phyzguy]

I think dumping the list into a vector will be easier, as well as more efficient.

How would you grade a homework problem where you asked the students to use linked lists, and someone returned a program using vectors? Would you give them full credit? I would not.

 

[dan2222]

Anyone might have written the full code?

 

[Halc]

Sure, but the algorithm is necessarily O(n^2) with a list. See how it runs with a million or so inputs.

An extract-sort is, sure, but I can think of O(n log(n)) ways to do it, still using nothing but linked lists.
As pointed out by others, I don't think finding a more complicated but scalable algorithm is the point of this exercise, but doing it with linked lists IS the point.

 

[Mark44]

Anyone might have written the full code?

That's not what we do here. Take a stab at writing the code yourself and we'll give you feedback, but we don't provide complete answers to posted questions.

 

[dan2222]

That's not what we do here. Take a stab at writing the code yourself and we'll give you feedback, but we don't provide complete answers to posted questions.

I know. I have really tried to, but I just don't know. Anyways, thank you

 

[Mark44]

I know. I have really tried to, but I just don't know. Anyways, thank you

Both Java and C# have linked list classes. What methods do these classes expose to programmers? That might be a good start. Have there been any similar examples shown in class?

 

[phyzguy]

I know. I have really tried to, but I just don't know. Anyways, thank you

If you, "have really tried to," please post the code you have tried. We can give feedback and advice.

 

[dan2222]

public static Node<int> MaxSequenceDelete(Node<int> lst)
{
Node<int> p = lst;

Node<int> del = p.GetNext();


while (p != null)
{
if (p.GetValue() < p.GetNext().GetValue())
{
p.SetNext(del.GetNext());
del.SetNext(null);
}

p = p.GetNext();
}
return del;
}

 

[rcgldr]

Sure, but the algorithm is necessarily O(n^2) with a list. See how it runs with a million or so inputs.

Merge sort for linked lists has time complexity O(n log(n)). For Java, you'll need to implement your own linked list, as Java's native linked list provides no equivalent of C++ std::list::splice(), which is used to move nodes within a list or from one list to another.

 

[willem2]

How would you grade a homework problem where you asked the students to use linked lists, and someone returned a program using vectors? Would you give them full credit? I would not.

If the end result is a linked list, as specified in the problem, I see no problem.