Given a linked list, zip it from its two ends in place, using constant extra space. The nodes in the resulting “zipped” linked list should go in this order: first, last, second, second last, and so on.

Implement functions to zip two linked lists and to unzip such that unzip(zip(L1, L2)) returns L1 and L2.

Example One

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Output: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> NULL

Example Two

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL

Output: 1 -> 5 -> 2 -> 4 -> 3 -> NULL

Constraints:

● 0

● -2 * 10^9

#### Solution

We've provided one solution:

1. Split the given list into halves so that, for example, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL becomes 1 -> 2 -> 3 -> NULL and 4 -> 5 -> 6 -> NULL.

2. Reverse the second list. In this example the second list becomes 6 -> 5 -> 4 -> NULL.

3. Now merge the two lists by alternating the nodes from first and second lists. Build the resulting list by updating the “next” pointers of the nodes.

O(n).

O(1).

##### Space Complexity:

O(n).

``````
// Reverse singly linked list in O(len) time and O(1) space.
{
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}

{
{
return NULL;
}
/*
Using slow-fast technique find the middle element.
If head: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL,
then slow should stop at 3.
*/
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
/*
Separate linked lists from the middle.
list1: 1 -> 2 -> 3 -> NULL
list2: 4 -> 5 -> 6 -> NULL
*/
/*
Till now:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL
With list1 pointing to 1, list2 pointing to 4 and slow pointing to 3.
Now break main linked list into two parts.
So do 3->next = NULL.
*/
slow->next = NULL;
/*
Reverse list2 so that from
list2: 4 -> 5 -> 6 -> NULL
it becomes
list2: 6 -> 5 -> 4 -> NULL
*/
/*
already declared "slow" and "fast", for example.
*/
/*
Merge list1 and list2.
list1: 1 -> 2 -> 3 -> NULL
list2: 6 -> 5 -> 4 -> NULL
merged: 1 -> 6 -> 2 -> 5 -> 3 -> 4 -> NULL
*/
while (list2)
{
next1 = list1->next;
next2 = list2->next;
list1->next = list2;
list2->next=next1;
list1 = next1;
list2 = next2;
}