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
4
  • 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 Commented Sep 21, 2015 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. Commented Sep 21, 2015 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. Commented 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... Commented Feb 6, 2018 at 17:43

1 Answer 1

Reset to default
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
5
  • And the starting index is zero, hence the length "-2" instead of "-1". Commented Sep 21, 2015 at 20:17
  • 12
    It's length-2 because you're removing two elements from the list, the first and the last. Commented 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. Commented Sep 21, 2015 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. Commented Sep 21, 2015 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. Commented Sep 22, 2015 at 9:38

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.