Note:

subproblem: reverse head and N2,

Key word:

reverse by pairs

//recursion
public class Solution {
  public ListNode reverseInPairs(ListNode head) {
    // corner case: empty list or single node
    if (head == null || head.next == null) {
      return head;
    }
    ListNode N2 = head.next;
    ListNode N3 = head.next.next;
    ListNode subHead = reverseInPairs(N3);
    N2.next = head;
    head.next = subHead;
    return N2;
  }
}

Complexity Analysis:

TC: O(n)

SC: O(n) call stack