Linked list returning root node in singly-linked list C

0
votes

I am writing a program to delete the nodes greater than x. I want to return the root node of the linked list after deleting. I save the new root node in variable "root". But unfortunately, when I get root in the main function, the value seems to be 0. Can anyone please help me identify the issue?**

// structure of a node
struct Node {
    int data;
    Node* next;
};

// function to get a new node
Node* getNode(int data)
{
  
    Node* newNode = (Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// function to delete all the nodes from the list
// that are greater than the specified value x
Node *deleteGreaterNodes(Node* head_ref, int x)
{
    Node *temp = head_ref, *prev;
    static Node *root;

    // If head node itself holds the value greater than 'x'
    if (temp != NULL && temp->data > x) {
        head_ref = temp->next; // Changed head
        free(temp); // free old head
        temp = head_ref; // Change temp
    }
    root = temp;
    // Delete occurrences other than head
    while (temp != NULL) {

        // Search for the node to be deleted,
        // keep track of the previous node as we
        // need to change 'prev->next'
        while (temp != NULL && temp->data <= x) {
            prev = temp;
            temp = temp->next;
        }

        // If required value node was not present
        // in linked list
        if (temp == NULL)
            return 0;

        // Unlink the node from linked list
        prev->next = temp->next;

        free (temp); // Free memory

        // Update Temp for next iteration of
        // outer loop
        temp = prev->next;
    }
    return head_ref;
}

// function to a print a linked list
void printList(Node* head)
{
    while (head) {
       
        printf("%d ",head->data);
        head = head->next;
    }
}

// Driver program to test above
int main()
{
    static Node *root;
    // Create list: 7->3->4->8->5->1
    Node* head = getNode(7);
    head->next = getNode(3);
    head->next->next = getNode(4);
    head->next->next->next = getNode(8);
    head->next->next->next->next = getNode(5);
    head->next->next->next->next->next = getNode(1);

    int x = 3;

   
     printf("Original List: "); 
    printList(head);

   root = deleteGreaterNodes(head, x);
     
     printf("\nModified List: "); 
    printList(root);

    return 0;
}
2
cstructlinked-listnodessingly-linked-list
You can't use cout << "Original List: "; in a C program. Don't use a C++ compiler to compile a C program. Since the rest of the code does seem to be C rather than C++, you can simply edit that line out (there's an equivalent printf() after it). But please be careful. - Jonathan Leffler
The last node in your ist has the value 1, which isn'r greater than three. In the inermost loop, you advance past all nodes you want to keep and if you reach the end, you return 0. So the code that returns 0 is right there, in your code. - M Oehm
I take it back — you are using another feature of C++ than just a stray cout. You define struct Node; in C++ that also defines a type Node, but it does not in C. You'd need typedef struct Node Node; or equivalent before defining the structure type. You shouldn't use static Node *root; in either place where it is used. In main(), it should be a simple local (automatic) variable. In deleteGreaterNodes(), it should be removed altogether. - Jonathan Leffler
Thanks @M Oehm . That was it ! I was returning 0 at the end . Now I changed it to return my head node. - pranathi

2 Answers

2
votes

For starters do not mix in one translation unit two languages C and C++.

Either write a C or C++ program.

For example this declaration in C

// structure of a node
struct Node {
    int data;
    Node* next;
};

is incorrect, You have to write

// structure of a node
struct Node {
    int data;
    struct Node* next;
};

There is no great sense to declare the static variable root

static Node *root;

and then one more variable head.

// Create list: 7->3->4->8->5->1
Node* head = getNode(7);

Your function deleteGreaterNodes is too complicated and as any complicated function it contains a bug in this code snippet

    // If required value node was not present
    // in linked list
    if (temp == NULL)
        return 0;

because it returns a null pointer instead of returning the pointer head_ref.

Here is your updated program that was adjusted according to the C language that contains a modified function deleteGreaterNodes.

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

// structure of a node
struct Node {
    int data;
    struct Node* next;
};

// function to get a new node
struct Node* getNode(int data)
{
  
    struct Node* newNode = ( struct Node * )malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// function to delete all the nodes from the list
// that are greater than the specified value x

struct Node *deleteGreaterNodes( struct Node* head_ref, int x )
{
    while ( head_ref && x < head_ref->data )
    {
        struct Node *tmp = head_ref;
        head_ref = head_ref->next;
        free( tmp );
    }
    
    if ( head_ref )
    {
        for ( struct Node *current = head_ref; current->next != NULL; )
        {
            if ( x < current->next->data )
            {
                struct Node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                current = current->next;
            }
        }
    }
    
    return head_ref;
}

// function to a print a linked list
void printList(struct Node* head)
{
    while (head) {
       
        printf("%d ",head->data);
        head = head->next;
    }
}

// Driver program to test above
int main()
{
    struct Node* head = getNode(7);
    head->next = getNode(3);
    head->next->next = getNode(4);
    head->next->next->next = getNode(8);
    head->next->next->next->next = getNode(5);
    head->next->next->next->next->next = getNode(1);

    int x = 3;

    printf( "Original List: " );
    // printf("Original List: "); 
    printList(head);

   head = deleteGreaterNodes(head, x);

    
     printf("\nModified List: "); 
    printList( head );

    return 0;
}

The program output is

Original List: 7 3 4 8 5 1 
Modified List: 3 1
2
votes

A simple way of implementing deleteGreaterNodes is to use an extra level of indirection to access the Node * links.

// function to delete all the nodes from the list
// that are greater than the specified value x
Node *deleteGreaterNodes(Node* head_ref, int x)
{
    Node **link = &head_ref; // Point to the pointer to the first node.
    Node *cur;

    while ((cur = *link) != NULL) {
        if (cur->data > x) {
            // The current node needs to be deleted from the list.
            // Change the link pointing to the current node to point to the next node.
            *link = cur->next;
            // Delete the current node.
            free(cur);
        } else {
            // The current node is to be kept on the list.
            // Get a pointer to the link to the next node.
            link = &cur->next;
        }
    }
    return head_ref;
}