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.

Consider a few scenarios and list out what you need to do to perform the swap in each of them.

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.

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.

Originally Posted by laserlight

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.