Given a linked list, reverse alternate nodes and append at the end.

Examples:

Input List:    1 -> 2 -> 3 -> 4 -> 5 -> 6

Output List: 1 -> 3 -> 5 -> 6 -> 4 -> 2

Input List:    1 -> 2 -> 3 -> 4 -> 5

Output List: 1 -> 3 -> 5 -> 4 -> 2

High level: 将处于奇数位置和偶数位置的Linked List断开，并且将偶数位置的LinkedList反向，再merge两个LinkedList，并return。

<aside> 💡 Trick: 用一个boolean isEven来判断这个ListNode需要接到哪个LinkedList里，每接完一个node重置这个boolean

</aside>

public class Solution {
  public ListNode reverseAlternate(ListNode head) {
    if (head == null || head.next == null || head.next.next == null) {
      return head;
    }
    ListNode evenHead = head;
    ListNode oddHead = head.next;
    ListNode evenCur = head;
    ListNode oddCur = head.next;
    ListNode cur = head.next.next;
    boolean isEven = true;
    while (cur != null) {
      if (isEven) {
        evenCur.next = cur;
        evenCur = cur;
      } else {
        oddCur.next = cur;
        oddCur = cur;
      }
      isEven = !isEven;
      cur = cur.next;
    }
    evenCur.next = null;
    oddCur.next = null;
    ListNode newOddHead = reverse(oddHead);
    evenCur.next = newOddHead;
    return evenHead;
  }

  private ListNode reverse(ListNode head) {
    ListNode prev = null;
    while (head != null) {
      ListNode next = head.next;
      head.next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
}

类似题：

[Odd Even Linked List](https://apricot-salsa-8ad.notion.site/Odd-Even-Linked-List-cabaaf5a13af4ed9b2b94134860955c4)