Por que 'length - 2' recursivamente fornece o centro de uma lista vinculada?

4

Estou lendo um livro de algoritmos e estou trabalhando em uma solução recursiva para a seguinte pergunta:

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

Esta é uma tarefa bastante fácil, mas o livro sugere uma solução recursiva que não consigo envolver minha cabeça. Afirma que para saber quando estamos no centro da lista encadeada, podemos realizar a seguinte operação:

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

Por que length - 2 recursivamente leva você ao meio? Alguém pode explicar isso em detalhes? Eu entendo que isso funciona, mas não matematicamente porque funciona.

    
por ApathyBear 21.09.2015 / 21:47
fonte

1 resposta

19

Se você avançar um passo e subtrair dois do comprimento, você receberá uma nova sub-lista com as extremidades removidas. Observe que o código não apenas subtrai do comprimento. Inicia a sub-lista em n.next .

Por exemplo, comece com a lista abcde, com comprimento 5. Na primeira iteração, você tem a sub-lista de comprimento 3 começando na segunda posição, ou bcd. No segundo, você obtém a sublista de comprimento 1 começando na segunda posição da sub-lista (a terceira posição da lista original), ou c. Como o comprimento é 1, você para e esta é a posição do meio.

    
por 21.09.2015 / 21:52
fonte