Simple Linked List Problem

This is a discussion on Simple Linked List Problem within the C++ Programming forums, part of the General Programming Boards category; I am to take two nodes, defined by: Code: struct Node{ string val; Node *next; }; And create a pointer ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    11

    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.

  2. #2
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,484
    what is the point of adding 3rd node?
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,406
    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

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    11
    Quote Originally Posted by vart View Post
    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.
    Quote 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.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by phantomotap View Post
    O_o

    How is this function called?



    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?
    I see now how I could have confused you. I was referring to the interface to a "swap two nodes" function. To do so by relinking nodes, you also need to pass in the node that points to the first node (if they are adjcaent), or if they aren't adjacent then you ned to pass in the pointer to the node before each node being swapped. This is so that you can actually relink them.

    Well good to hear that the OP believes the problem is solved. I think I'm now left a little confused about what the sortPair function actually does. It seems like it's for merging two individual items into a two-item list. Well nevermind, I guess we'll hear more later if there are other issues.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,406
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  2. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  3. doubly linked list problem
    By YevGenius in forum C Programming
    Replies: 4
    Last Post: 05-02-2004, 09:54 PM
  4. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 06:46 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21