92. Reverse Linked List II

Problem Statement

Pattern:

---

Solution

// successor is the continuation of non-reversed LL
ListNode successor = null;
 
public ListNode reverseBetween(ListNode head, int l, int r) {
	if (l == 1) return reverseN(head, r);
	
	head.next = reverseBetween(head.next, l - 1, r - 1);
	return head;
}
 
ListNode reverseN(ListNode head, int n) {
	if (n == 1) {
		successor = head.next;
		return head;
	}
	ListNode last = reverseN(head.next, n - 1);
	head.next.next = head;
	head.next = successor;    // instead of pointing to null, point to successor
	return last;
}

Notes

• recursively call reverseBetween with head.next and at l == 1, return reverse (head, r)
• r will have reduced by l , so exit condition for n==1
• set successor node, and the rest is like 206. Reverse Linked List