AnswerBun.com

Splitting C linked list without making a copy

Stack Overflow Asked on December 24, 2020

I have this struct:

typedef struct node {
    struct node *m_Next;
    int id;
} NODE;

And I need to split linked list in half. If it can’t be split into two same halves, I want to remove the last one from the bigger list.

Example: The whole list: {1,2,3,4,5}; What I need: A:{1,2} B:{3,4} (The last one is discarded)

I have this function to separate the list:

void split(NODE *src, NODE **p1, NODE **p2) {
    int len = get_length(src);
    if (len < 2) {
        *p1 = NULL;
        *p2 = NULL;
        return;
    }
    struct node *current = src;
    int c = (len - 1) / 2;
    for (int i = 0; i < c; i++) {
        current = current->m_Next;
    }
    *p1 = src;
    *p2 = current->m_Next;
    current->m_Next = NULL;
}

It works fine with even lists, but when I try to separate something with 7 structs, I have two problems:

a) The last one doesn’t point to NULL
b) It shuffles the data somehow (I expect: A:{1,2,3} B:{4,5,6} | I get: A:{1,2,3} B:{5,4,7} for example)

Could anyone please help me splitting the list correctly and adding the even/odd condition?

I already have the function to delete the last struct:

deleteNode(struct TSoldier *firstNode)

I just don’t use it currently, because the split function is bugged.

Thanks 🙂

2 Answers

First of all, it is worth noting that the following code probably causes a memory leak:

if (len < 2) {
    *p1 = NULL;
    *p2 = NULL;
    return;
}

If the number of nodes is equal to 1, then, unless you keep some other reference to this node, the memory will be leaked. You probably have such a reference outside the function, but you are probably discarding this reference and only keeping the values written to p1 and p2, which means the memory is leaked.

Therefore, assuming that you allocated the node with malloc, you will probably want to add the line

free( src );

in order to prevent the memory leak, or use your function deleteNode.

As already pointed out in the other answer, the line

int c = (len - 1) / 2;

is wrong. It should be:

int c = len / 2 - 1;

At the end of your function split, if the number of nodes is odd, you must add code to discard the final node, for example like this:

if ( len % 2 == 1 )
{
    current = *p2;
    for (int i = 0; i < c; i++) {
        current = current->m_Next;
    }
    free( current->m_Next );
    current->m_Next = NULL;
}

Answered by Andreas Wenzel on December 24, 2020

To determine the last node of the first half, instead of int c = (len - 1) / 2; you should use this formula that works for even and odd lengths:

int c = len / 2 - 1;

Similarly, to drop the last node if the length is odd and greater than 1:

if (len & 1) {
    NODE *node = src;
    for (int i = 2; i < len; i++) {
        node = node->m_Next;
    }
    deleteNode(node->m_Next);
    node->m_Next = NULL;
}

Here is an alternative approach using the fast and slow scan trick:

void split(NODE *src, NODE **p1, NODE **p2) {
    NODE *last = src;
    *p1 = *p2 = NULL;
    if (src && src->m_Next) {
        NODE *slow = src;
        NODE *fast = src;
        while (fast->m_Next && fast->m_Next->m_Next) {
            slow = slow->m_Next;
            fast = fast->m_Next->m_Next;
        }
        *p1 = src;
        *p2 = slow->m_Next;
        slow->m_Next = NULL;
        last = fast->m_Next;  // last will be non NULL if length is odd
        fast->m_Next = NULL;
    }
    if (last) {
        deleteNode(last);  // drop the last node if required
    }
}

Answered by chqrlie on December 24, 2020

Add your own answers!

Related Questions

Change null to 0 in response

1  Asked on December 3, 2021 by edwin-landsfield

   

Print complete SQL for all queries made by objection.js

2  Asked on December 3, 2021 by eugene-kim

 

Easiest way to convert a char* of hex to actual hex in C?

1  Asked on December 3, 2021 by purplespark

 

Xcode confused with IQAir Api Parsing

1  Asked on December 3, 2021 by unkowncoder

       

gRPC server cannot be built and throws error

0  Asked on December 3, 2021 by jibo_libin

   

How to correctly map huge json file to Java (pojo)?

1  Asked on December 3, 2021 by orkhan-hasanli

     

check all items in csv column except one [python pandas]

2  Asked on December 2, 2021 by blindside044

       

Unpivot a single into two rows – T-SQL

1  Asked on December 2, 2021 by error-1004

       

Ask a Question

Get help from others!

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP