class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode sentry = new ListNode(0);
        sentry.next = head;
        ListNode prev = sentry;
        while (head != null && head.next != null) {
            ListNode q = head.next;
            head.next = q.next;
            q.next = head;
            prev.next = q;
            prev = head;
            head = prev.next;
        }
        return sentry.next;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        ListNode p = head;
        head = head.next;
        ListNode last_p = null;
        while (p != null && p.next != null) {
            ListNode q = p.next;
            p.next = q.next;
            q.next = p;
            if (last_p != null) {
                last_p.next = q;
            }
            last_p = p;
            p = p.next;
        }
        return head;
    }
}