Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.
题意：反转链表的指定一段。
思路：这道题是Reverse Linked List的followup，把反转整个链表限定为反转指定一段。可以把反转的解法套在指定范围上，反转之后还要把它和原来的两端连接起来，所以需要记录一下两端连接的节点，以及反转后的这段链表的头尾节点。
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null || head.next == null || m < 0 || n <= m) {
return head;
}
ListNode root = new ListNode(0);
root.next = head;
//连接反转段的端点
ListNode left = root;
ListNode right = new ListNode(0);
//反转段的左右端点
ListNode rLeft = new ListNode(0);
ListNode rRight = new ListNode(0);
//反转需要的两个指针
ListNode pre = new ListNode(0);
ListNode cur = new ListNode(0);
for (int i = 0; i < m - 1; i++) {
left = left.next;
}
rRight = left.next;
pre = left.next;
cur = pre.next;
for (int i = 0; i < n - m; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
rLeft = pre;
right = cur;
left.next = rLeft;
rRight.next = right;
return root.next;
}