Note:

将奇数node和偶数node分开

用一个boolean来判断当前node是奇数还是偶数

接好 奇数node和偶数node后，将他们断开联系，并将它们连起来，return odd Head；

Key word:

public class Solution {
  public ListNode oddEvenList(ListNode head) {
    //corner case: empty list or single node
    if (head == null || head.next == null) {
      return head;
    }
    ListNode oddHead = head;
    ListNode evenHead = head.next;
    ListNode oddCur = oddHead;
    ListNode evenCur = evenHead;
    ListNode cur = head.next.next;
    boolean isOdd = true;
    while (cur != null) {
      if (isOdd) {
        oddCur.next = cur;
        oddCur = cur;
      } else {
        evenCur.next = cur;
        evenCur = cur;
      }
      isOdd = !isOdd;
      cur = cur.next;
    }
    evenCur.next = null;
    oddCur.next = evenHead;
    return oddHead;
  }
}

Complexity Analysis:

TC: O(n)

SC: O(1)