Thread: Linked List - Swapping Nodes

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174

    Linked List - Swapping Nodes

    I'm trying to implement a selection sort algorithm on linked lists, and the trouble I've ran into is swapping any two nodes in the linked list.

    My selection sort function:

    Code:
    void selSortLL(NodeT *head) {
        NodeT *cur = NULL;
        NodeT *move = NULL;
        NodeT *min = NULL;
        
        if (head == NULL || head->next == NULL) {
            return head;
        }
        
        for (cur = head; cur->next != NULL; cur=cur->next) {
            min = cur;
            for (move = cur->next; move != NULL; move=move->next) {
                if (move->value < min->value) {
                    min = move;
                }
            }
            if (min != cur) {
                //SWAP CUR W/ MIN NODES
            }
        }
        
        return head;
    }
    I'm sure I'd need at least one temporary node, but even then I'm still unsure about how I'm going to tackle this problem.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Consider a few scenarios and list out what you need to do to perform the swap in each of them.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Ok well if I have a situation where each of the nodes I'm swapping are not adjacent to each other or at the ends of the list, then if the nodes are a and b, it'll be something like this:

    ... -> a- -> a -> a+ -> ... -> b- -> b -> b+ -> ...

    And so if I let a = tmp1, b = tmp2, each way I try to rearrange the links, I'm always going to break the list. I just can't wrap my head around this.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Mentallic
    if I have a situation where each of the nodes I'm swapping are not adjacent to each other or at the ends of the list (...) each way I try to rearrange the links, I'm always going to break the list
    Give the nodes nice names with a concrete example, e.g.,
    A -> B -> C -> D -> E -> F

    So, you want to swap B and E such that you end up with:
    A -> E -> C -> D -> B -> F

    Hence:
    • A's next pointer must be changed to point to E
    • B's next pointer must be changed to point to F
    • D's next pointer must be changed to point to B
    • E's next pointer must be changed to point to C

    From the above list, it is immediately clear what nodes you need to have on hand in order to modify where their next pointer points to.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Mar 2010
    Location
    Australia
    Posts
    174
    Quote Originally Posted by laserlight View Post
    Give the nodes nice names with a concrete example, e.g.,
    A -> B -> C -> D -> E -> F

    So, you want to swap B and E such that you end up with:
    A -> E -> C -> D -> B -> F

    Hence:
    • A's next pointer must be changed to point to E
    • B's next pointer must be changed to point to F
    • D's next pointer must be changed to point to B
    • E's next pointer must be changed to point to C

    From the above list, it is immediately clear what nodes you need to have on hand in order to modify where their next pointer points to.
    Ahh thanks for that. So I do need to have tmp1=B and tmp2=E nodes but I need to change my code so that I can also have access to A and D.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Sorting/Swapping
    By swinters in forum C Programming
    Replies: 5
    Last Post: 02-24-2011, 01:15 AM
  2. swapping nodes in double linked list
    By a0161 in forum C Programming
    Replies: 15
    Last Post: 10-30-2008, 06:12 PM
  3. Help with swapping nodes in a linked list
    By Axel in forum C Programming
    Replies: 3
    Last Post: 10-18-2005, 09:16 AM
  4. Linked List and Nodes
    By paperbox005 in forum C++ Programming
    Replies: 2
    Last Post: 08-04-2004, 09:12 AM
  5. Replies: 10
    Last Post: 10-18-2002, 06:35 AM