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
Read full article from Code Arena: Zip of a linked list
No comments:
Post a Comment