Splitting linked list

[alex067]

I have an assignment where I have to split the linked list at a given position by the user.

The linked list looks as such:
15 -> 0 -> 15 -> 10 -> 20 -> 30 -> 60 -> NULL;

User wants to split the link at node 3:
15 -> 0 -> 15 -> NULL;
10 -> 20 -> 30 -> 60 -> NULL;


The problem arises when I ask the user to enter what node to split it, the output is always 15. So it's always showing the very first node and deleting everything else

I cannot use deep copy to copy the new link into a whole new node, I have to do this using pointers only and delinking/re-linking

void TheNode::split(int choice)
{
	MyNode *current = head;
	MyNode *second = new MyNode;
	if (!head) //if empty simply return
	{
		return;
	}
	if (choice == 1)
	{
		second = head;
		second->next = NULL;
		current->next = head->next;
	}
	for (int i = 0; i < choice - 1; i++)
	{
		current = current->next;
		second -> next = current; //once it reaches the desired positoin
	}
	second = current->next;
	second->next = NULL;
	current = head;
	current->next = NULL;

	current = second = NULL;
}

int main()
{
	int pos, val;
	val = 15;

	TheNode one;
	one.add(10);
	one.add(20);
	one.add(30);
	one.display();
	cout << endl;
	one.addFront(0);
	one.addEnd(60);
	one.display();
	cout << endl;

	cout << "Replace " << val << " at what node position: " << endl;
	cin >> pos;

	one.insert(val, pos);
	one.display();
	cout << endl;
	
	cout << "Split the node at what node position?" << endl;
	cin >> pos;
	one.split(pos);
	one.display();

	system("PAUSE");
	return 0;

	
}

[Duthomhas]

Drawing pictures helps a lot:

Before:

        +---+   +---+   +---+   +---+   +---+
 head-->|   |-->|   |-->|   |-->|   |-->|   |-->NULL
        +---+   +---+   +---+   +---+   +---+

After:

                         head2
                          |
                          V
        +---+   +---+   +---+   +---+   +---+
 head-->|   |-->|   |   |   |-->|   |-->|   |-->NULL
        +---+   +---+   +---+   +---+   +---+
                  |
                  V
                 NULL 

Your professor would like to see two lists when you are done, and for you to print them both out. Your code should look something like:

	TheNode* one = new TheNode(10);
	one->add(20);
	one->add(30);
	...

	// Split the first list into two lists
	TheNode* two = one.split(pos);

	// Display the two lists
	one.display();
	two.display();

	// Don't forget to clean up!
	one.free();
	two.free();

Therefore, the method should have the following prototype:

TheNode* TheNode::split(int pos)

The function is being asked to do two things. Find a position and separate two nodes. I would personally have another function which simply finds an indexed node:

TheNode* TheNode::find(int pos)

but that isn't strictly necessary. But that's me.

Let's review:

        +---+   +---+   +---+   +---+   +---+
 head-->|   |-->|   |-->|   |-->|   |-->|   |-->NULL
        +---+   +---+   +---+   +---+   +---+

becomes

                         head2
                          |
                          V
        +---+   +---+   +---+   +---+   +---+
 head-->|   |-->|   |-->|   |-->|   |-->|   |-->NULL
        +---+   +---+   +---+   +---+   +---+

then becomes

                         head2
                          |
                          V
        +---+   +---+   +---+   +---+   +---+
 head-->|   |-->|   |   |   |-->|   |-->|   |-->NULL
        +---+   +---+   +---+   +---+   +---+
                  |
                  V
                 NULL 

which is the same as

        +---+   +---+
 head-->|   |-->|   |-->NULL
        +---+   +---+

         +---+   +---+   +---+
 head2-->|   |-->|   |-->|   |-->NULL
         +---+   +---+   +---+

Hope this helps.

[alex067]

Yes the pictures make things a lot more clearer.

Is my split function correct? It keeps only outputting the very first value of the new list

[alex067]

Also, what do you mean we need to "free" the nodes? Are you saying we need to de-link them?

[Duthomhas]

Is my split function correct?

No, your split function does not do the things it should. Hence the reason for my very long post above.

Are you saying we need to de-link them?

Anything you allocate with new you must deallocate with delete.

I presume your TheNode::add() method creates new nodes using operator new, right?