# The many learnings of a seemingly straightforward LinkedList problem

2021.05.10

Here’s a seemingly simple LinkedList problem that utilizes the fast and slow pointer technique and some basic Linked List manipulation. But going down the rabbit hole of understanding every component of this problem proved to be more than I expected.

Here’s the problem: Given a linked list, take the second half of the list (if it has an odd number of nodes, then take the second of the middle nodes), reverse it, and then interweave those nodes with the first half of the list.

Example 1: Input: a > b > c > 1 > 2 > 3 Output: a > 3 > b > 2 > c > 1

Example 2: Input: 1 > 3 > 5 Output: 1 > 5 > 3

After some initial analysis, it’s clear that the problem can be solved by running three subroutines:

1. Split the list into two lists
2. Reverse the second list
3. Interweave the first with the second list

List reversal and interweaving the two lists are less tricky, so let’s get those out of the way.

``````const reverse = function(head) {
let prev = null;

}

return prev;
}
``````

One interesting observation I made along the way is the value of the head node once the `reverse` function has ran. Suppose we have a print function in the class `Node` to observe the chnages in nodes.

``````class Node {
constructor(val, next = null) {
this.val = val;
this.next = next;
}

print() {
let temp = this;
while (temp) {
console.log(temp.val);
temp = temp.next;
}
}
}
``````

If we run the input from Example 1 (a > b > c > 1 > 2 > 3), we observe a change in the `head` node.

``````head.print(); // a > b > c > 1 > 2 > 3
let reversed = reverse(head); // 3 > 2 > 1 > c > b > a
``````

I then realized that when we copy a Linked List, we are not deep cloning the data structure but merely creating a new head with shared nodes, kind of like this. So when we have initialized fast and slow pointers and assigned them to point to the same nodes as `head`, we are still very much working with the same nodes. So during the reversal process, we move the pointer with the newly initialized nodes, backwards, yet the initial head remains at the head of the original node `a`, except that at end of the reversal process, it’s now pointing at `null`.

Prior to reversing the list

``````a > b > c > 1 > 2 > 3 > null
^
``````

After reversing the list

``````3 > 2 > 1 > c > b > a > null
^                   ^
``````

Next, we interweave two lists, one representing the first half and the other the second half of the list.

``````const merge = function(l1, l2) {
while (l2) {
nextNode = l1.next; // save the next node before redirecting the pointer
l1.next = l2; // redirect the pointer to the other list
l1 = nextNode; // move up the current pointer to the saved one above

nextNode = l2.next; // same as above, save the next pointer before repointing the pointer
l2.next = l1; // repoint the next pointer to the other list
l2 = nextNode; // current list needs to jump position to saved pointer above
}
}
``````

Then we come to the first item on the list, which is the method responsible for splitting the original list in two.

1. In order to provide the second half of the list for both odd and even numbered nodes of LL, we set up the `while` loop to stop one node before the middle of the list is reached. The assigned variable to `slow.next` will always return the correct node at the middle of the list regardless of whether the LL is even or odd numbered.
2. Instead of reassigning `slow = slow.next` and retunring `slow` to the main method as the split second part of the array, here we assign the node to the start of the second half of the list to a new variable. This allows us to move the pointer to the head `slow` to null, which means that the current head now will stop once it reaches the middle of the list. This way, we end up with two “clean” lists representing the first and second halfs of the list for processing later on.
``````const split = function(head) {