[Java] Zip singly linked list

List zipping means interleaving the list nodes from the top and bottom of a given list to create a new list.

Eg with this input list:

A -> B -> C -> D

the zipping is:

A -> D -> B -> C

Doing this in constant space and quadratic time is trivial, but there is a better solution that avoids scanning the list every time with two pointers running one ahead of the other to find the current last element in the list.

Again as with most linked list problems, the correct handling of the pointers is the trickiest part. The idea is to spend some time to preprocess the list in O(N) time to split it in two halves, and reverse the second half; this way, we now simply need to walk both lists and interleave the nodes in order to produce our result.


Finding the middle point is easy using the fast and slow pointers method .

First gotcha: after finding the middle point, remember to use slow.next to mark the start of the second half and then set it to null to truncate the list there!

The code to reverse a singly linked list efficiently can be found here.

After the list is split and the second half is reversed, use two pointers to track the current elements in both lists, plus an auxiliary element to handle the switching. Based on the way we find the half point, the second half will never have more elements than the first half; this is an important note for the looping we'll do later.

The logic then is as follows:

As long as there are elements in the second half, keep interleaving starting from the second half!

1) track the next element from the last
2) link the next last element to the next first
3) link the next first element to the last element
4) move the first pointer to the next element passing through the added node!
5) move the last element to the tracked one

Easier with a picture maybe. F (first) is pointer to the current element in the first list, L (last) is pointer to the current element in the second list, T is temp node

Input is:

A -> B -> C -> D -> E

1st iteration:

F points to A -> B -> C
L points to E -> D

1st step, T points to D (E -> D)

2nd step, link E -> B
3rd step link A -> E
4th step F points to B passing through E (A -> E -> B)
5th step L points to T which was pointing to D

the partial result is:

A -> E -> B -> C

2nd iteration:

1st step T points to null (D -> null)
2nd step, link D -> C
3rd step, link B -> D
4th step F points to C passing through D (B -> D -> C)
5th step L points to T which was pointing to null

the partial result is:

A -> E -> B -> D -> C

And since L is now pointing to null, there are no more elements in the second half of the list, therefore we have our output.

This logic sound complicated, but it translates to 6 lines of code, parenthesis excluded.. magic!

You can check more singly and doubly linked lists utilities on my Gist along with some test cases in ZipListJTests.