class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null) return null;
        ListNode oddSentry = new ListNode(0);
        ListNode evenSentry = new ListNode(0);
        ListNode p = oddSentry;
        ListNode q = evenSentry;
        ListNode oddPtr = head;
        ListNode evenPtr = null;
        while (oddPtr != null) {
            p.next = oddPtr;
            evenPtr = oddPtr.next;
            oddPtr.next = null;
            p = p.next;

            if (evenPtr != null) {
                q.next = evenPtr;
                oddPtr = evenPtr.next;
                evenPtr.next = null;
                q = q.next;
            } else {
                break;
            }
        }
        p.next = evenSentry.next;
        return oddSentry.next;
    }
}