DaniWeb Forum Index > Software Development > C

C RSS

Recrusive Split on a linked list

•

Join Date: Feb 2007

Posts: 1

Reputation: alt234 is an unknown quantity at this point

Solved Threads: 0

alt234

Offline

Newbie Poster

Recrusive Split on a linked list

Feb 10th, 2007

I'm trying to write a recursive merge sort on a linked list. I'm basically stuck on the split portion of it currently. I came up with a solution quite similar to many other solutions I've found on the web. Many people say it works but so far my solution doesn't seem to. Here is my split code:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
LLN* LLN::split() {
    if(next == NULL) return NULL;
    LLN* ret = this->next;
    this->next = ret->next;
    ret->next = ret->next->split();
 
    return ret;
}
LLN* LLN::split() {
    if(next == NULL) return NULL;
    LLN* ret = this->next;
    this->next = ret->next;
    ret->next = ret->next->split();

    return ret;
}

Now, here is my problem. This does seem to split the list, but the list I wish to return just gets lost for some reason. For example, the following data is inserted into the list...
a
b
c
d
e
f
g

When printed each list, I should have the output for one list be...
g
e
c
a

The other should be
f
d
b

The ret list should be the "f d b" one. However, when from that code snippet, I return "ret" or "this" they both give the output "g e c a." I've tried to retrieve the f d b list but it seems to be lost. I've drawn this algorithm out on paper a hundred times and I can't figure it out what is wrong. Any ideas about this?