Splitting C linked list without making a copy

Question

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 :)

Andreas Wenzel · Answer

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;
}

chqrlie · Answer

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
    }
}

Splitting C linked list without making a copy

2 Answers

Add your own answers!

Ask a Question