Swap nodes in a linked list without swapping data

Question

how can i use pointers without copying the data? I want to write a bubble sorting function, but I got stuck, and need some help how to swap node addresses instead of values. I have a file with city names, and temperatures:

• Las Vegas, 25
• New York, 33
• Chicago, 23
• Houston, 39

and I need to sort it by the temperature, and write it to another file.

UPDATE: Ok, now I think i understand the theoratical part:

// p is my node
// p-prev -> p -> p-next -> p-next-next
prev->next = p->next;
p->next = p->next->next;
prev->next->next = p;

This is what i need to do, to swap the nodes, but syntactically i couldnt make it work.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node {
    char name[128];
    int id;
    struct node *next;
}*head;

void readFile() {
    char fnamer[128] = "";
    printf("\nEnter the file name to read (delimiter: ,): \n");
    scanf("%s",&fnamer);
    FILE *inf = fopen(fnamer, "r");

    char buffer[1024];
    memset(buffer, 0, 1024);
    while(fgets(buffer, 1024, inf)){
        struct node *temp = malloc(sizeof(struct node));
        temp->next = NULL;

        if(sscanf(buffer, "%19[^,], %d", temp->name, &temp->id) != 2){
            free(temp);
            break;
        }

        if(!head){
            head = temp;
        } else{
            temp->next = head;
            head = temp;
        }
    }

    fclose(inf);
}

int main(void) {
    // Read a linked list from file
    readFile();

    //Bubble sort in linked list
    struct node *loop1 = head;
    while(loop1){
        struct node *loop2 = loop1->next;
        while(loop2){
            if(loop1->id > loop2->id){

                // Swap next pointers
                // This is not working
                struct node *temp = loop1->next;
                loop1->next = loop2->next;
                loop2->next  = temp;

            }
            loop2 = loop2->next;
        }
        loop1 = loop1->next;
    }

    // Print the sorted linked list to file:
    char foutname[100]="";
    printf("\nPlease Enter the file name to write the result: \n");
    scanf("%s",&foutname);

    FILE *outf;
    outf = fopen(foutname, "w+");

    loop1 = head;
    while(loop1){
        printf("%s %d\n", loop1->name, loop1->id);
        fprintf(outf, "%s %d\n", loop1->name, loop1->id);
        loop1 = loop1->next;
    }
    fclose(outf);
    return 0;
}

Answer 1

We need to swap the next links such that the link chain is rearranged. If you swap node1 and node2, the link chain should change as follows:

//change the link chain from
node0 -> node1 -> node2 -> node3
//to
node0 -> node2 -> node1 -> node3

We put this inside a while loop and the loop breaks when there are no more swaps. We can improve this function by limiting the number comparisons. After each loop, the last element should be sorted.

To put this together,lets use typedef keyword so that we don't have to repeat struct everywhere.

typedef struct node_t
{
    char name[20];
    int id;
    struct node_t *next;
} node;

void bubblesort(node **list)
{
    if(!(*list)) return;
    node *previous_node = NULL;
    node *sort_up_to = NULL;
    while(1)
    {
        previous_node = NULL;
        node *ptr = *list;
        node *last_change = NULL;
        while(ptr->next)
        {
            //the rest of the list is sorted?
            if(sort_up_to && ptr == sort_up_to) break;

            node *next = ptr->next;
            if(ptr->id > next->id)
            {
                if(previous_node == NULL)
                    *list = next;
                else
                    previous_node->next = next;
                ptr->next = next->next;
                next->next = ptr;
                last_change = next;
            }

            previous_node = ptr;
            ptr = next;
        }

        //list is all sorted?
        if(!last_change) break;

        sort_up_to = last_change;
    }
}

int main(void)
{
    node* head = NULL;

    FILE *fin = fopen("test.txt", "r");
    if(!fin)
        return 0;

    node temp;
    while(fscanf(fin, "%19[^,], %d\n", temp.name, &temp.id) == 2)
    {
        node *n = malloc(sizeof(node));
        n->next = NULL;
        strcpy(n->name, temp.name);
        n->id = temp.id;
        if(head)
            n->next = head;
        head = n;
    }
    fclose(fin);

    bubblesort(&head);

    for(node* n = head; n != NULL; n = n->next)
        printf("%s %d\n", n->name, n->id);

    return 0;
}

Answer 2

To swap two nodes in a singly-linked list you can use the following function

void swap(struct node **current)
{
    struct node *tmp = (*current)->next->next;
    (*current)->next->next = *current;
    *current = (*current)->next;
    (*current)->next->next = tmp;
}

For example to swap the head node and the next node you can call the function like

swap( &head );

See also my answer at this reference Bubble sort in c linked list where there is shown how to write the bubble sort algorithm for a singly-linked list.