Doubly­linked lists help!

[hyperdolphin99]

I am needing to split a list. I want the list to split into two list, one list will have values less than the target and the other will have values greater than the target. So this function receives a pointer to the first node of a doubly­linked list and a target data value, and passes back the pointers to the first nodes of two newly created doubly­linked lists.
Example:
target value = 7
List = 1 3 5 6 9 4 19

less list = 1 3 5 6 4
greater list = 9 19

How could this work?

[doug4]

This looks like handling the pivot for quicksort. You can look up the algorithm.

Either:
1. Create 2 new lists and move the nodes from the first list into the correct list
2. Swap elements in the list so that the little values are at one end of the list, and split the list into 2.

[dhayden]

What is supposed to happen to the original list? In other words, are you moving the nodes from the original list to new lists, or are you making new nodes for the new lists, so that the original list remains unchanged?

If you're just moving the items then the basic algorithm is:

while (origList.head) {
    // unlink the first item from origList
    // add it to the one of the new lists.
}

[hyperdolphin99]

The original list needs to remain unchanged.

[dhayden]

Thanks. Please show whatever code you have so far. Are you using std::list for this or are you using your own doubly linked list code? So pseudo-code for what you need to do is:

create list low;
create list high;
for each node in the original list
    if (node value > target) {
        add a node to list "high" with value = target
   } else {
        add a node to list "low" with value = target
}