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

First of all, take a pencil and some paper, draw a simple list using squares for nodes and arrows for the links (or pointers in general). Then erase and remove the links as needed on paper to "execute" the operation. Once you've got it working on paper, then you sit down and try to implement it in code, statement by statement. Build and test between every statement, step through the code in a debugger to verify it does what's needed. — Some programmer dude, Dec 20 '20 at 20:49

Andreas Wenzel · Answer 1 · 2020-12-21T00:43:05.180

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 2 · 2020-12-21T08:55:36.907

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

Since most people won't understand the so-called `-->` "operator", see [this link](https://stackoverflow.com/questions/1642028/what-is-the-operator-in-c) for an explanation. — Andreas Wenzel, Dec 20 '20 at 22:57

Splitting C linked list without making a copy

2 Answers2