Thread: Dividing a linked list in half recursively

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    12

    Dividing a linked list in half recursively

    I'm pretty sure I'm on the right track with this, it's simply a method to split a linked list in half, setting it up for a merge sort. My intent is to split the list like this:

    a->b->c->d->e

    so that the new lists are a->c->e and b->d (I want it to actually return a pointer to the start of the second list, in this example, b)

    Code:
    Node *Node::split() {
    	if (next == NULL) return this;               // if next is null, return this as list cannot be split further
    	Node *n = this->next;                         // create node that points to the node after this
    	this->next = n->next;                          // connects this to the node after this->next
    	n->next = n->next->split();                 // calls split from the new node position
    	return n;
    }
    I need to get some other working code before I can test this method, so I just wanted to see if I was on the right track. Thoughts/suggestions are appreciated

  2. #2
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    This will work, however this line will cause a crash if you ever have an even number of nodes:
    Code:
    n->next = n->next->split();    //n->next can be NULL

  3. #3
    Registered User
    Join Date
    Sep 2004
    Posts
    12
    Ah, good point, so wouldl this added if statement do the trick?

    Code:
    Node *Node::split() {
    	if (next == NULL) return this;               // if next is null, return this as list cannot be split further
    	Node *n = this->next;                         // create node that points to the node after this
    	this->next = n->next;                          // connects this to the node after this->next
            if (n->next !=NULL) n->next = n->next->split();                 // calls split from the new node position
    	return n;
    }

  4. #4
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    Indeed it will. As a side note, this algorithm is a bit odd. Not to say it's bad, I think it's quite clever, however I did not understand what you were trying to do without walking through the code. You're comments don't explain what you're trying to do, they only convert the code into English. Just a thought =)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM