content: // https://leetcode.com/problems/reorder-list
  // T: O(N)
  // S: O(1)
  
  public class ReorderList {
      public void reorderList(ListNode head) {
          if (head == null || head.next == null) return;
  
          ListNode middle = getMiddleOfLinkedList(head);
          ListNode preMiddle = reverseLinkedList(middle);
          interleaveNodes(head, preMiddle);
      }
  
      private ListNode getMiddleOfLinkedList(ListNode head) {
          ListNode p1 = head;
          ListNode p2 = head;
          while(p2.next!=null&&p2.next.next!=null){
              p1 = p1.next;
              p2 = p2.next.next;
          }
          return p1;
      }
  
      private ListNode reverseLinkedList(ListNode head) {
          ListNode preCurrent = head.next;
          while(preCurrent.next != null){
              ListNode current = preCurrent.next;
              preCurrent.next = current.next;
              current.next = head.next;
              head.next = current;
          }
          return head;
      }
  
      // 1->2->3->6->5->4 to 1->6->2->5->3->4
      private void interleaveNodes(ListNode head, ListNode preMiddle) {
          ListNode p1 = head;
          ListNode p2 = preMiddle.next;
          while(p1 != preMiddle){
              preMiddle.next = p2.next;
              p2.next = p1.next;
              p1.next = p2;
              p1 = p2.next;
              p2 = preMiddle.next;
          }
      }
  }
  