CODEWITHSUNDEEP
cmemorylinked-list
RandomBeginner
RandomBeginner

Reputation: 562

Extra node after filling a linked list in C

I have an integer (ex: 123) and I need to store it reversely (digit by digit) in a linked list. But I seem to have an extra digit at the end of the list. For example: 807 needs to be stored as "7 -> 0 -> 8" But my output is "7 -> 0 -> 8 -> -1094795586'.

This is for the leetcode problem "Add Two Numbers".

//I need to fill "l" with result (reversed)

void FillList(struct ListNode* l, unsigned long long int result)
{
    struct ListNode *newNode = l;
    newNode->val = 0;
    while(result != 0)
    {
        newNode->val = result % 10;
        result /= 10;
        newNode->next = malloc(sizeof(struct ListNode));
        newNode = newNode->next;
    }
    newNode->next = NULL;
}

Output is "7 -> 0 -> 8 -> -1094795586', instead of "7 -> 0 -> 8".

Upvotes: 1

Views: 83

Answers (3)

Ivin J
Ivin J

Reputation: 11

In your case head node l is not equal to NULL always. And assuming that your head node l is NULL and your code can be

void FillList(struct ListNode* l, unsigned long long int result){
    struct ListNode *newNode = NULL,*pNode=NULL;
    do{
      newNode=malloc(sizeof(struct ListNode));
      newNode->val = result % 10;
      newNode->next = NULL;
      if(l==NULL){
         l=newNode;
         p=newNode;
      }else{
         p->next=newNode;
      }
    }while((result /= 10)>0);
}

Upvotes: 1

Aconcagua
Aconcagua

Reputation: 25526

Assume our result to create is simply 7:

newNode->val = 0; // sets l to 0, OK so far
while(result != 0) // true!
{
    newNode->val = result % 10; // gets changed to 7
    newNode->next = malloc(sizeof(struct ListNode)); // you create a new node!
                                                     // (without assigning a value to it!)
    // now getting back to the while, discovering that you won't enter it again
    // but the next node is already created!
}

You need to avoid this surplus node. One possible way (minimal changes to your code):

struct ListNode* newNode = l;
for(;;)
{
    newNode->val = result % 10;
    result /= 10;
    if(result == 0)
        break;
    // at this point we now KNOW that we yet need another node, so we create it
    newNode->next = malloc(sizeof(struct ListNode));
    newNode = newNode->next;
}
newNode->next = NULL;

You'll discover that the very first assignment to l (when newNode still points to the same node) covers the special case of 0 as well, as both 0 % 10 and 0 / 10 still remain 0...

Upvotes: 2

Schwern
Schwern

Reputation: 164819

The problem is you're always allocating a new next node even if there is no next value.

while(result != 0)
{
    newNode->val = result % 10;
    result /= 10;
    newNode->next = malloc(sizeof(struct ListNode));  // <<<<<<-----
    newNode = newNode->next;
}

This is a bit tricky because you want to allocate a note on each iteration, but you already start with an allocated node making the first iteration a special case.

We can work around this by remembering what the previous node was.

void FillList(struct ListNode* node, unsigned long long int num)
{
    struct ListNode* prev = NULL;
    do {
        // Since prev starts NULL this only happens the second time.
        if( prev ) {
            prev->next = node = malloc(sizeof(struct ListNode));
        }
        node->val = num % 10;

        // It's safer to always ensure everything is initialized.
        node->next = NULL;
        num /= 10;

        // Store the current node as the previous one.
        prev = node;
    } while(num != 0);
}

Also by using a do/while loop we ensure it always runs once, even if num starts at 0. This eliminates 0 as a special case.

Upvotes: 1

Related Questions