// Iteration public ListNode iterationSolution(ListNode head, int m, int n) { if (m == n) return head; ListNodedummy=newListNode(-1); dummy.next = head; ListNodep= head; ListNodeprev= dummy; intcount=1; while (count < m) { // before m prev = p; p = p.next; ++count; } // now: p -> m-th node ListNodemthNode= p; while (count < n) { // between m and n p = p.next; ++count; } // now: p -> n-th node ListNoderest= p.next; // the nodes after n-th node p.next = null; ListNodetailNode= mthNode; mthNode = reverse(mthNode); prev.next = mthNode; tailNode.next = rest; // connect the rest of the nodes return dummy.next; }

private ListNode reverseAmong(ListNode x, int m, int n, int count) { if (count >= n) { // points to the n-th node return x; } if (count < m) { // not within range x.next = reverseAmong(x.next, m, n, count + 1); return x; } if (count == m) { // points to the m-th node ListNodenthNode= reverseAmong(x.next, m, n, count + 1); ListNoderest= nthNode.next; // nodes that after n-th nthNode.next = null; // make the list m~n. Set null for reverse ListNodetailNode= x; x = reverse(x); // reverse the m~n nodes tailNode.next = rest; // rest = null / nodes that are after n-th return x; } // points to the nodes between (m, n) return reverseAmong(x.next, m, n, count + 1); }

Time: $O(N)$ Space: $O(N)$ in the worst case when we have to reverse the entire list.