CODEWITHSUNDEEP
clistpointerssplit
Katrina Lala
Katrina Lala

Reputation: 9

Split linked list into half

I am trying to create a function splitlist(), which will split a singly linked list into two sublists – one for the front half, and one for the back half. I have come up with a code below which will work for the first time that I call the function, but when I call the function repeatedly, the program crashes. Any advice on how I can change my code to prevent such an error? The function splitlist() is void as it prints two lists which contains frontList and backList.

typedef struct _listnode {
int item;
struct _listnode *next;
} ListNode;         

typedef struct _linkedlist {
int size;
ListNode *head;
} LinkedList;   

    void splitlist(LinkedList* list1, LinkedList * firsthalf, LinkedList *secondhalf)       
{
    ListNode *cur = list1->head;
    ListNode *front = firsthalf->head;
    ListNode *back = secondhalf->head;
    int totalnodes = list1->size;
    int i;
    if (totalnodes % 2 != 0)                    //if odd number of elements, add 1 to make it easier for traversal of list
    {
        totalnodes = totalnodes + 1;
    }
    int halfnodes = totalnodes / 2;


    {
        for (i = 0; i < halfnodes; i++)             
        {
            if (firsthalf->head == NULL)        //initialise the head
            {
                firsthalf->head = malloc(sizeof(ListNode)); //create first node
                front = firsthalf->head;
            }
            else
            {
                front->next = malloc(sizeof(ListNode));     
                front = front->next;                        
            }
            front->item = cur->item;                    // insert value from list1 into firsthalf
            cur = cur->next;                            //point to next node in list1

        }
        front->next = NULL;     //last node

        for (i = halfnodes; i < totalnodes; i++)            
        {
            if (secondhalf->head == NULL)
            {
                secondhalf->head = malloc(sizeof(ListNode));
                back = secondhalf->head;
            }
            else
            {
                back->next = malloc(sizeof(ListNode));
                back = back->next;
            }
            back->item = cur->item;
            cur = cur->next;

        }
        back->next = NULL;
    }

}

Upvotes: 0

Views: 4561

Answers (3)

Paul Ogilvie
Paul Ogilvie

Reputation: 25286

At first glance I can't see much wrong with your code (assuming the assignment is to create copies of the list nodes in the new half lists), so the error could be in how you call the function, as an exmple, that could be:

LinkedList mainlist= {0};
LinkedList firsthalf= {0}, secondhalf= {0};

//mainlist got filled somehow; we now want to split

firsthalf->List= malloc(sizeof(ListNode));
secondthalf->List= malloc(sizeof(ListNode));
memset(firsthalf->List, 0, sizeof(ListNode));
memset(secondhalf->List, 0, sizeof(ListNode));
splitlist(&mainlist, &firsthalf, &secondhalf);

Upvotes: 0

Eugene Anisiutkin
Eugene Anisiutkin

Reputation: 140

There are many things wrong with this code. First of all malloc return values are not checked, malloc can fail. And i strongly suspect that because of malloc fail your programm stops. You repeatedly allocate the memory inside the function, but do you free it when you do not need it anymore? Why do yo use malloc at all? As posted earlier you do not need to.

Please post how the function is called, because it is really unclear how LinkedList* list1, LinkedList * firsthalf, LinkedList *secondhalf are used. Also it is unclear what is the structure of LinkedList is.

Upvotes: 1

Kalu
Kalu

Reputation: 290

why use malloc?It will create a new list.But we want to split the list. I guess firsthalf and second half are NULL

void splitlist(LinkedList* list1, LinkedList * firsthalf, LinkedList *secondhalf)       
{
    ListNode *cur = list1->head;
    ListNode *front;
    int totalnodes = list1->size;
    int i;
    if (totalnodes % 2 != 0)                    //if odd number of elements, add 1 to make it easier for traversal of list
    {
        totalnodes = totalnodes + 1;
    }
    int halfnodes = totalnodes / 2;

    firsthalf->head=list1->head;
    front=firsthalf->head;

    for(i=0;i<halfnode;i++)
         front=front->next; 

     secondhalf->head=front->next;
     front->next=NULL;        

}

Upvotes: 0

Related Questions