4

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.

|improve this question
  • 3
    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 '15 at 19:52
  • 1
    The code is copied from the book. I am asking why it works mathematically, I am not looking to change it. – ApathyBear Sep 21 '15 at 19:55
  • 6
    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. – Stephen Sep 22 '15 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... – Deduplicator Feb 6 '18 at 17:43
19

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.

|improve this answer
  • And the starting index is zero, hence the length "-2" instead of "-1". – OKAN Sep 21 '15 at 20:17
  • 12
    It's length-2 because you're removing two elements from the list, the first and the last. – Davislor Sep 21 '15 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 '15 at 20:27
  • 15
    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. – Davislor Sep 21 '15 at 20:35
  • 3
    @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. – Vatine Sep 22 '15 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.