The key part is "reverse" method.
Also it can be used in the Reverse K group.
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode temp = dummy;
int i = 1;
//Find the prev
while( temp != null && i < m) {
temp = temp.next;
i++;
}
ListNode prev = temp;
//Find the next
while (temp != null && i <= n) {
temp = temp.next;
i++;
}
ListNode next = temp.next;
reverse(prev, next);
return dummy.next;
}
private void reverse(ListNode prev, ListNode next) {
ListNode last = prev.next;
ListNode curr = last.next;
while (curr!=next) {
last.next = curr.next;
curr.next = prev.next;
prev.next = curr;
curr = last.next;
}
}
No comments:
Post a Comment