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.

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 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.