Thread: Simple Linked List Problem

I am to take two nodes, defined by:

Code:

struct Node{
    string val;
    Node *next;
};

And create a pointer node to a list of those two nodes sorted alphabetically. It's a simple assignment, but apparently something's going awry. The incoming values of the node's next is irrelevant, but the output matters and the last node in the list must point to null.

Code:

Node* sortPair (Node* p1, Node* p2)
{
    assert(p1!=NULL);
    assert(p2!=NULL);
    Node *p3 = new Node;
    if (p1->val <= p2->val) {
        p3->next = p1;
        p1->next = p2;
        p2->next = NULL; }
    else {
        p3->next = p2;
        p2->next = p1;
        p1->next = NULL; }
    return p3;
}

I am failing a test of some sort (and the only clue as to what it tests is 'pointers'), but I can't tell what I did wrong.
Help is very much appreciated.

O_o

How is this function called?

I'll tell you now that any [...] relinking nodes is very hard.

I'm confused by this. Are you talking about sorting any given range in a singly linked list? Are you talking about the potential interface to the sorting algorithm? Or the potential interface to a "swap these two nodes" function that may be called by the algorithm?

Insertion Sort is the best thing to [...] sorting algorithm.

If you allow sorting of an arbitrary range you'll still need three parameters. (Four parameters if you want to be reasonable.)

I'm not arguing that it isn't probably the best for a beginner. It is not like it is much more difficult to understand than "bubblesort", or that it isn't a decent general purpose sort. I'm just not getting the parameter thing and what it has to do with the algorithm of choice. (I understand it in the context of the first post, but not what that has to do with the choice of algorithm.)

Soma

Originally Posted by vart

what is the point of adding 3rd node?

Hahaha, oh, man. The way the question was worded, I thought I had to create a pointer to the list and not just start the list off with the first value. Getting rid of the third node solved the issue.

Originally Posted by iMalc

So, you're trying to sort a linked-list correct?

I'll tell you now that any linked-list algorithm to relink nodes so that they are swapped is way harder than you realise. To swap two adjacent nodes you actually need three parameters, and to swap two non-adjacent nodes you need four. So no, you can't just allocate the third node inside this function, you actually have to pass it in. Even if you get that part correct, you'll almost certainly get the rest of the algorithm wrong. Even trying to get BubbleSort 100% correct by relinking nodes is very hard.

If all you have to do is to sort a linked list, don't use an algorithm that performs swaps. Use an algorithm that is built on simply inserting and removing nodes. Insertion Sort is the best thing to use for a simple first-time linked-list sorting algorithm.

In actuality, the two nodes are not already in a linked list, as both come in with their next fields NULL. However, I am very thankful of this advice and will keep it in mind for the future, as this sounds like a mistake I'd probably make.

I see now how I could [...] that you can actually relink them.

I get that. I just read your post as somehow tying that simple fact to "BubbleSort". I was having problems with that.

I think I'm now left a little confused about what the sortPair function actually does.

I'm curious as well.

Soma