Coding Problem 6

Este problema fue preguntado por Google.

Dada una lista enlazada simple, intercambia sus valores cada dos posiciones y retorna la lista.

Por ejemplo, dado 1 -> 2 -> 3 -> 4, devuelve 2 -> 1 -> 4 -> 3.

Solución:

Bueno este problema, es también sencillo de entender, como siempre vamos a empezar por algunos tests sencillos.

public class ProblemTest {

    @Test
    public void givenEmptyListShouldReturnEmptyList() {
        assertEquals(Problem.orderList(List.nil()), List.nil());
    }

    @Test
    public void shouldReturnListOrdered() {
        List<Integer> numbers = List.of(1, 2, 3, 4);

        assertEquals(Problem.orderList(numbers), List.of(2, 1, 4, 3));
    }
}

Ahora, de primeras se me ha ocurrido este código mínimo y sencillo para pasar estos tests:

public class Problem {

    public static List<Integer> orderList(List<Integer> numbers) {
        List<Integer> result = new ArrayList<>();

        for (int index = 0; index < numbers.size(); index++) {
            if (isPairPosition(index)) {
                int aux = numbers.get(index);
                result.add(index, numbers.get(index + 1));
                result.add(index + 1, aux);
            }
        }

        return result;
    }

    private static boolean isPairPosition(int index) {
        return index % 2 == 0;
    }
}

Como podéis ver no entraña demasiada dificultad, existen métodos como el Collections.swap() que te cambia elementos en una lista, quizás seria meter demasiada complejidad a algo tan sencillo computacionalmente hablando. Si te ha gustado te espero en el próximo Coding Problem, no será tan sencillo ;)