Like Tree1Likes
  • 1 Post By laserlight

Linked List - Swapping Nodes

This is a discussion on Linked List - Swapping Nodes within the C Programming forums, part of the General Programming Boards category; I'm trying to implement a selection sort algorithm on linked lists, and the trouble I've ran into is swapping any ...

  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
    20,975
    Consider a few scenarios and list out what you need to do to perform the swap in each of them.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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
    20,975
    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.
    poornaMoksha likes this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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, 12: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

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