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--;
}

Unsolved!!

Here are some questions which I will try in coming days and have not solved them. Will take them of this list as I solve each one of them :).

• Given a linked list structure where every node represents a linked list and contains two pointers of its type: (i) pointer to next node in the main list. (ii) pointer to a linked list where this node is the head. Write a function to flatten the list into a single linked list.


• You are given an array of integers A[1..n] and a maximum sliding window of size w. Output an array B where B[i] is the maximum in A[i, i+w-1].


• You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.


• Given a binary matrix of NxN of integers ,return only unique rows of binary arrays eg: 01001 10110 01001 11100 ans: 01001 10110 11100


• Given an array of integers like ar[]= {1,3,2,4,5,4,2}. Create another array ar_low[] such that ar_low[i] = # of elements lower than or equal to ar[i] in ar[i+1:n-1]. So the output for above array should be {0,2,1,2,2,1,0}

Reverse a Linked List!!

Iterative version

void reverse()
{
    if(head == NULL)
        return;
    list *first = NULL;
    list *second = head;
    list *third = second->next;
    while(third!=NULL)
    {
        second->next=first;
        first = second;
        second = third;
        third = third->next;
    }
    second->next = first;
    head=second;
}

Recursive version

void rReverse(list *n)
{
    if (n == NULL)
        return;
    if(n->next ==NULL)
    {
        head = n;
        return ;
    }
    rReverse(n->next);
    n->next = n;
}