Zip of a linked list

Given a linked list <1, 2, 3, 4, 5, 6>, zip of this linked list is defined as 1, 6 , 2, 5 , 3, 4. And the task is to achieve desired linked list using O(1) space.
This can be performed by a simple algorithm:

• Split the list from the middle into two lists. We are splitting the list into two and not creating a new linked list hence maintaining O(1) space
• Now we have two lists : 1, 2, 3 and 4, 5, 6. Reverse the second list
• This gives us two lists 1, 2, 3 and 6, 5, 4
• Now merge the lists picking one node from each list as a time

Below is how we can do the same using STL lists.

list<int> l; //original list
list<int> nl; //new empty list
int size = l.size();

//Step 1 of splitting into two
for(int i = 0 ; i < size/2; i++)
{
    nl.push_back(l.back());
    l.pop_back();
}

//At this point we have 1, 2, 3 and 6, 5, 4
size = l.size();
list<int>::iterator it = l.begin();
it++;
while(i)
{
    l.insert(it, nl.front());
    nl.pop_front();
    i--;
}

Count number of occurences of a number in a sorted array

We will use the fact that the array is sorted. Hence we can use binary search. The only trick is that we do not stop when we find the first occurrence of the number, but continue doing the binary search to the left and right of that number.

int count(int* arr, int num, int start, int end)
{
    if(start > end)
    return 0;
    int mid = (start + end)/2;
    if(arr[mid] == num)
        return 1 + count(arr, num, start, mid-1) + count(arr, num, mid+1, end);
    else if(arr[mid] > num)
        return count(arr, num, start, mid-1);
    else
        return count(arr, num, mid+1, end);
}