http://programming-puzzle.blogspot.com/2014/02/zip-of-linked-list.html
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:
Solution from EPI
public static <T> Node<T> zippingLinkedList(Node<T> L) {
Node<T> slow = L, fast = L, preSlow = null;
// Find the middle point of L.
while (fast != null) {
fast = fast.next;
if (fast != null) {
preSlow = slow;
fast = fast.next;
slow = slow.next;
}
}
if (preSlow == null) {
return L; // only contains one node in the list.
}
preSlow.next = null; // splits the list into two lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
Node<T> curr = L;
// Zipping the list.
while (curr != null && reverse != null) {
Node<T> temp = curr.next;
curr.next = reverse;
curr = temp;
// Connect curr->next to reverse, and advance curr.
// connectANextToBAdvanceA(ref_curr, reverse);
if (curr != null) {
// Connect reverse->next to curr, and advance reverse.
Node<T> temp2 = reverse.next;
reverse.next = curr;
reverse = temp2;
// connectANextToBAdvanceA(ref_reverse, curr);
}
}
return L;
}
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
Solution from EPI
public static <T> Node<T> zippingLinkedList(Node<T> L) {
Node<T> slow = L, fast = L, preSlow = null;
// Find the middle point of L.
while (fast != null) {
fast = fast.next;
if (fast != null) {
preSlow = slow;
fast = fast.next;
slow = slow.next;
}
}
if (preSlow == null) {
return L; // only contains one node in the list.
}
preSlow.next = null; // splits the list into two lists.
Node<T> reverse = ReverseLinkedListIterativeTemplate
.reverseLinkedList(slow);
Node<T> curr = L;
// Zipping the list.
while (curr != null && reverse != null) {
Node<T> temp = curr.next;
curr.next = reverse;
curr = temp;
// Connect curr->next to reverse, and advance curr.
// connectANextToBAdvanceA(ref_curr, reverse);
if (curr != null) {
// Connect reverse->next to curr, and advance reverse.
Node<T> temp2 = reverse.next;
reverse.next = curr;
reverse = temp2;
// connectANextToBAdvanceA(ref_reverse, curr);
}
}
return L;
}