Перемешать элементы в списке

Дан однонаправленный связный список L: L₀→L₁→…→L_n-1→L_n,
Надо перемешать его элменты в следующем порядке: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

То есть первый, последний, второй, предпоследний и т.д.

Нельзя модифицировать значения val в ячейке, можно только менять указатели.

Пример 1:

Дан список 1->2->3->4, перемешиваем его так: 1->4->2->3.

Example 2:

Дан список 1->2->3->4->5, перемешиваем его так: 1->5->2->4->3.

Идея решения
Нам нужно сделать три шага:

1. разбить исходный список на две равные части;
2. вторую часть развернуть, см. Развернуть связный список
3. сформировать новый список, добавляя в результат попеременно то элемент из первого списка, то из второго.

Компилируемое решение

class Solution {
  public void reorderList(ListNode head) {
  if (head == null || head.next == null)
      return;
  
  // step 1. находим середину списка и его конец
  // prev - это хвост первой половины списка (середина исходного списка)
  // slow  - это голова второй половины
  ListNode prev = null, slow = head, fast = head, l1 = head;
  
// если указатель slow движется элемент за элементом, а указатель fast перепрыгивает
// через 2 элемента, то 
//когда fast дойдёт до конца списка, slow будет как раз на середине
  while (fast != null && fast.next != null) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
  }
  
  prev.next = null; // хвост первой половины должен быть последним и не указывать никуда
  
  // step 2. разворачиваем вторую половину
  ListNode l2 = reverse(slow);
  
  // step 3. объединяем обе половины
  merge(l1, l2);
}

// процедура разворота второй половины списка (см. предыдущую статью)
ListNode reverse(ListNode head) {
  ListNode prev = null, curr = head, next = null;
  
  while (curr != null) {
    next = curr.next; // temp
    curr.next = prev; // разворот
// проходим дальше по списку
    prev = curr; 
    curr = next;
  }
  
  return prev;
}

// процедура объединения списков
private static void merge(ListNode head1, ListNode head2) {
    while (head2 != null) {
// запоминаем следующий элемент из первого списка
        ListNode next = head1.next;
// в первом списке на месте следующего ставим текущий элемент из второго списка
        head1.next = head2;
// продвигаемся по первому списку на добавленный элемент, 
// к которому прикрепим следущий
        head1 = head2;
// а следующий должен быть тот, что мы запомнили из первого списка
        head2 = next;
// и так чередуемся пока не достигнем конца списка
    }
}}