Related List: Bubble Sort Pointers (C)

Question

I am working on a university assignment. I am trying to write a sorting of linked lists in C. I am not allowed to change values ​​- only pointers.

Here is my sort function:

struct node *sort_list(struct node *head) { bool swapped ; struct node *cur = head, *first ; if ( head == NULL || head->next == NULL ) return head ; else { do { swapped = false ; while ( cur != NULL && cur->next != NULL ){ if (cur->value > cur->next->value){ cur = swap_with_next( cur ) ; swapped = true ; } cur = cur->next ; } } while (swapped == true) ; } return head ; } 

And the swap function:

  struct node *swap_with_next(struct node *n) { struct node *tmp ; tmp = n ; n = n->next ; tmp->next = n->next ; n->next = tmp ; return n ; } 

Problem: wrong conclusion:

 input: 5->2->NULL output: 5->NULL input: 9->1->5->2->8->3 output: 9->5->8 

Any help would be greatly appreciated!

Answer 1

So, let's say there are 3 nodes A, B and C (in that order). You are trying to swap B and C. So, you are passing a pointer to B to the swap function. Now all pointer manipulations are correct, but you are missing one thing. The next pointer should point to C when you finish the swap. You never installed it. When you finish the swap function, the next pointer still points to B, which is obviously wrong. This is problem.

Answer 2

You return a pointer that is good, but in a swap you are manipulating a copy of the pointer, not the “actual” one you are trying to change. You are trying to manipulate a parameter to replace inside swap, but this is only a change to the copy of this node that was created when the function was called. This parameter must be a pointer to a pointer if you want to change it inside a function.