c - Linked List Function? -

so i'm writing function makes smallest node @ end of linked list. far works except last element. if linked list created nodes containing items 0~9, list after function {1,2,3,4,5,6,7,8,0,9} , 0 not become @ end.

any ideas why?

my function;

int connecting(linkk a) {     linkk l = a;     (int = 0; i<sizeof(l);i++)     {         if (l->item < l->next->item)         {             int = l->item;             l->item = l->next->item;             l->next->item = a;             l = l->next;         }         else{l=l->next;}     }     return 0; } 

let's start think should doing differently:

1. the name of function connecting. given description of you'd function do, not name.
2. i can infer usage linkk typedef'ed pointer. hiding pointers way not idea, of time.
3. your function returns int. it's 0. why? not make sense.
4. because linkk pointer node, , pass head pointer value (i.e. copy of it) function, you're unable handle case head of list minimum. either return "new" head pointer, or pass pointer head pointer able modify head pointer.
5. your use of sizeof wrong, suggested. sizeof(l) give size (in chars) of pointer, 8 on 64 bit system or 4 on 32 bit system.
6. you're not changing nodes, rather moving values in between nodes. ok if it's want do, description of algorithm suggest want move node instead.
7. your function doing much, imo. can hard split, better approach separate finding / extracting minimum , putting @ end of list.
8. you're modifying lot more wanted to. consider list 1, 2, 3, 0, 4. using algorithm, list changed 2, 3, 1, 4, 0. doing not bad performance, surprising caller. surprises aren't when comes programming!

so, let's implementation, step step:

struct node {   int item;   struct node * next; }; 

i assume want move node containing minimum value end of list, in description. i'm going keep single function receiving struct node * head pointer, despite point above, in order keep closer original code. let's out special / base cases first: moving minimum element of empty list of single element list trivial: nothing.

if (head == null || head->next == null) {   return head; } 

i'm returning "new" head of list allow caller update it's own head pointer. (as said, head copy of caller's head pointer, modifying not have effect @ call site).

because we're dealing singly linked list here, , implementation should not unnecessarily iterate on list, should remember node we've visited. otherwise couldn't extract node list:

struct node * follow, * point; 

follow follows directly behind point.

initially, place point second node of list (we checked there @ least 2 nodes in list). follow point head:

point = head->next; follow = head; 

since want find minimum item, need keep track of minimum of searched part of list. initialize head node's value:

int currentminimum = head->item; 

now we're ready iterate on list, in order find node containing minimum. need not find node containing minimum, 1 before , 1 after it, in order able extract easily. so, 3 pointers:

struct node * predecessor, * minimum, * successor;

as set currentminimum heads item, should set pointers accordingly:

predecessor = null; // nothing preceding head minimum = head; successor = head->next; 

now let's iterate, moving point on list, until falls off @ end:

while (point != null) {   // continued   follow = point;   point = point->next; } // when we're here, follow point last node 

in each iteration, need check if found smaller value current minimum, , remember node containing it:

if (point->item < currentminimum) {   predecessor = follow;   minimum = point;   successor = point->next;   currentminimum = point->item; } 

now, when out of loop, following state should reached:

• minimum points node containing minimum.
• follow points last node of list.
• the 2 above same, special case!
• predecessor still null, special case!

considering first special case of minimum = follow: in case, minimum @ end of list, profit! otherwise, need "cut" node @ minimum out of list , append last node, pointed follow:

if (follow != minimum) {   if (predecessor != null) {     predecessor->next = successor; // cut out     minimum->next = null; // last node     follow->next = minimum; // append @ end   } else {     // continued   } } 

as can see, there's second special case consider: if predecessor still null, no item smaller heads item. (therefore, test minimum == head) thus, first node of list moved end. need inform caller this!

head = head->next; // second node first one, though not need do, see further down! minimum->next = null; // last node follow->next = minimum; // append @ end 

since assignment head changed function parameter (which copy of pointer function has been called), need return (possibly modified!) head pointer, giving caller ability update own head pointer:

return head; 

a caller use function so:

struct node * head = get_a_fancy_list(); head = move_minimum_to_end(head); // our function being called! 

finally, thing consider: can see, moving node (instead of item) more complicated. need modify @ least 2 pointers in order achieve want. in contrast: moving item value requires 2 modifications of item values (and iterating easier). moving node instead of item makes sense when pointer assignments faster item assignments. since items of type int not case here.

moving item instead of node containing item considerably easier. first of all, need keep track of minimum (value node):

struct node * minimum; int currentminimum; 

to iterate, we're again going use 2 pointers. can done single one, code going more readable way:

struct node * point, * follow; 

we start off same initial state:

minimum = head; currentminimum = head->item; follow = head; point = head->next; 

iterating similar other implementation, iteration step:

while (point != null) {   if (point->item < currentminimum) {     minimum = point;     currentminimum = point->item;   }   follow = point;   point = point->next; } // follow points last node 

now, doing same previous implementation, can swap items of last node , node minimum:

minimum->item = follow->item; follow->item = currentminimum; // contains minimum->item 

there's no point in checking follow != minimum in previous approach: it, swapping item of node own item won't harm. otoh adding if add branch, , possible performance penalty.

since didn't change list structure (the linking between nodes), there's not more consider. don't need inform caller new head, there never change it. style purposes, i'd add either way:

return head; 

ok, got bit long now, it's easy understand!