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.
Follow up:
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
Notes:
Constraints:
● 0 <= number of nodes<= 100000
● -2 * 10^9 <= value in any node <= 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.
Time Complexity:
O(n).
Auxiliary Space Used:
O(1).
Space Complexity:
O(n).
// Reverse singly linked list in O(len) time and O(1) space.
LinkedListNode *reverse_linked_list(LinkedListNode *cur)
{
LinkedListNode *prev = NULL;
LinkedListNode *next;
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
LinkedListNode *zip_given_linked_list(LinkedListNode *head)
{
if (head == NULL)
{
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.
*/
LinkedListNode *slow = head;
LinkedListNode *fast = head->next;
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
*/
LinkedListNode *list1 = head;
LinkedListNode *list2 = slow->next;
/*
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
*/
list2 = reverse_linked_list(list2);
/*
For readability we declare two new pointers instead of reusing
already declared "slow" and "fast", for example.
*/
LinkedListNode *next1;
LinkedListNode *next2;
/*
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;
}
return head;
}
