Member Avatar for alt234

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
  • 120 Views
  • 1 Month Discussion Span
  • Latest Post Latest Post by thinkfast
Member Avatar for thinkfast

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.