0

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:

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?

2
Contributors
1
Reply
2
Views
10 Years
Discussion Span
Last Post by thinkfast
0

I think this is head of one list and ret is head of the other one, using both would give you the splitted lists

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.