insertSortedList

[yyuuvvaall]

hi,

can someone understand how the new element is being attached to the list in this code?

void insertSortedList (Node **head, int value)
{
/* creating a new node */
 
Node *ptr = createNode (value);
Node **pCurrent = head;
 
/* adding the new node to the correct place in the list */
while (*pCurrent != NULL && (*pCurrent)->val < ptr->val)
        pCurrent = &( (*pCurrent)->next );
 
ptr->next = *pCurrent;
*pCurrent = ptr;
}

I refer spcifically to the last two lines.

thanks

[SpS]

I guess there's some problem here

*pCurrent = ptr;

This will break your list.
You need another pointer. Maybe this will help:-

void insertSortedList (Node **head, int value)
{
/* creating a new node */
 
Node *ptr = createNode (value);
Node **pCurrent = head;
[B]Node **ptemp; [/B]
/* adding the new node to the correct place in the list */
while (*pCurrent != NULL && (*pCurrent)->val < ptr->val)
        [B]ptemp=pCurrent,[/B]pCurrent = &( (*pCurrent)->next );
ptr->next = *pCurrent;
[B]ptemp=[/B] ptr;
}

Let me know if it works or not.

[yyuuvvaall]

the problem is that this code works perfectly. I just don't understand why.
you can try it yourself. I think this is all you need :

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _Node{
int val;
struct _Node *next;
} Node;
 
Node* createNode (int value)
{
/* allocating the memory */
 
Node *ptr = (Node*) malloc (sizeof(Node));
/* checking that memory was indeed allocated */
assert (ptr != NULL);
 
/* initializing */
ptr->val = value;
ptr->next = NULL;
 
return ptr;
}
 
void insertSortedList (Node **head, int value)
{
/* creating a new node */
Node *ptr = createNode (value);
Node **pCurrent = head;
 
/* adding the new node to the correct place in the list */
while (*pCurrent != NULL && (*pCurrent)->val < ptr->val)
pCurrent = &( (*pCurrent)->next );
 
ptr->next = *pCurrent;
*pCurrent = ptr;
}

yyuuvvaall.

[yyuuvvaall]

try this main for exmple:

int array[10] = {1,4,6,2,5,8,7,9,0,3};
Node  *sorted_head = NULL;
int i;
/* initializing the lists with the elements in the array */
for (i = 0; i < 10; ++i)
{
insertSortedList (&sorted_head, array[i]);
}

and then use:

void printList (Node *head)
{
/* going over the element and printing each one */
while (head != NULL)
{
printf ("%d ", head->val);
head = head->next;
}
}

[dude543]

void insertSortedList (Node **head, int value)
{
/* creating a new node */
 
Node *ptr = createNode (value);
Node **pCurrent = head;
 
/* adding the new node to the correct place in the list */
while (*pCurrent != NULL && (*pCurrent)->val < ptr->val)
        pCurrent = &( (*pCurrent)->next );
 
ptr->next = *pCurrent;
*pCurrent = ptr;
}

The first this function runs head equals NULL.

Node *ptr = createNode (value); /* ptr points to a new cell */
Node **pCurrent = head; 
 
/* while loop will exit right a way because head = NULL */
while (*pCurrent != NULL && (*pCurrent)->val < ptr->val)
        pCurrent = &( (*pCurrent)->next );
 
/* ptr ->next = *pCurrent */
ptr->next = *pCurrent;
/* The head points to the first cell */
*pCurrent = ptr;

Try to run the function in your head. as in this senrio :
the list contains 4 cells and is orderd : 1, 3, 7, 9
The new value to add is 4.
At the end you will get 1, 3, 4 , 7, 9

/* ptr->next will point on cell 7 */
ptr->next = *pCurrent;

/* The next pointer of 3 will point on ptr */
*pCurrent = ptr;