Splitting a linked list

Given a linked list, write code to split it into two lists, each containing the alternate (odd-even) nodes from the original. If the original list is

The It should split into two lists like below

To make the final output look like (breaking the original list in two sublists)

Solution:

There can be few solutions, both similar to each other (with cosmetic differences)

1. Traverse the list and delete alternate nodes from it and append the node to a new list. The original list will be left with odd nodes and new list will have all the even nodes.

2. Keep two pointers. Traverse the original list and append alternate nodes to the end of each pointer. This will destroy the original list and the two pointers will have odd and even nodes.

3. If you don't want to destroy the original list, then in method-2, instead of deleting the nodes make an extra copy of node and append it to alternate nodes.

Below is the code for point-2. 

I am sure you can manage other parts. Its essentially about deleting the node from one place and putting it at another, isn't it :)

Code:

Keeping global variables is not a good idea. I have kept the two (head1 & head2) global for the sake of simplicity

    Node* head1 = NULL;
    Node* head2 = NULL;
    void alternateSplit(Node* head)
    {
        if(head==NULL) return;
        // Setting the first 2 nodes as heads of
        head1 = head; head2 = head->next;
        if(head2 == NULL) return;
        // First two nodes are considered. Start from 3rd
        head = head->next->next;
        // Pointers pointing to the end of list 1 and 2
        Node* end1 = head1;;
        Node* end2 = head2;
        int t=1; // To mark alternate
        for(; head != NULL; head=head->next, t*=-1)
        {
            if(t == 1)
            {
                end1->next = head;
                end1 = end1->next;
            }
            else
            {
                end2->next = head;
                end2 = end2->next;
            }
        }
        end1->next = end2->next = NULL;
    }

More problems on linked lists:

• http://cslibrary.stanford.edu/105/LinkedListProblems.pdf