# Why does `length - 2` recursively give you the center of a linked list?

I am reading through an Algorithms book and am working through a recursive solution to the following question:

Implement a function to check if a linked list is a palindrome

This is an easy enough task, but the book suggests a recursive solution that I can't seem to wrap my head around. It states that to know when we are at the center of the linked list, we can perform the following operation:

``````recurse(Node n, int length) {
if (length == 0 || length == 1) {
return [something]; // At middle
}
recurse(n.next, length - 2);
...
}
``````

Why does `length - 2` recursively get you to the middle? Can someone explain this in detail? I understand that it works, but not mathematically why it works.

• the code snippet looks syntactically incorrect, have you tried to run / debug it? or at least to compile. See also How to ask “how to understand some code” questions
– gnat
Sep 21, 2015 at 19:52
• The code is copied from the book. I am asking why it works mathematically, I am not looking to change it. Sep 21, 2015 at 19:55
• I think this is more "how does this algorithm work" than "how does this code work". The difference is subtle, but I would answer this one on a whiteboard if asked this question at work. I think that makes it fair game for Programmers over SO. Sep 22, 2015 at 0:01
• That's bad code. Convert it to tail-recursive to avoid blowing the stack, and it looks like it would probably still O(n²), which is bad... Feb 6, 2018 at 17:43

If you advance one step and subtract two from the length, you get a new sublist with the ends removed. Observe that the code does not just subtract from the length. It starts the sublist at `n.next`.

For example, start with the list abcde, with length 5. On the first iteration, you have the sublist of length 3 starting at the second position, or bcd. On the second, you get the sublist of length 1 starting at the second position of the sublist (the third position of the original list), or c. Since length is 1, you stop, and this is the middle position.

• And the starting index is zero, hence the length "-2" instead of "-1".
– OKAN
Sep 21, 2015 at 20:17
• It's length-2 because you're removing two elements from the list, the first and the last. Sep 21, 2015 at 20:22
• I am not saying otherwise, just trying to clarify that in order to remove "one" element from the end you have to subtract "2" from the length since the starting index is "zero". The OP was asking about this part specifically.
– OKAN
Sep 21, 2015 at 20:27
• That's orthogonal to whether the starting index is 0 or 1. The length of the new sublist is two elements shorter regardless of where you count from. Sep 21, 2015 at 20:35
• @OmarK No, you subtract two because the list you are interested in is two elements shorter (it is without "the first" and "the last" element). This is independent of if the list "index" (these look as if they could well be implemented with linked lists) being 0-based or 1-based. After all, if I have a list [1, 2, 4] or a list [0, 1, 2, 3] (both length 4) both [2, 3] and [1, 2] are lists of length 2, as well as being the previous lists with the first and last element removed. Sep 22, 2015 at 9:38