Input: 1 -> 2 -> 3 -> 4 -> 5 -> null, m = 2, n = 4 Step1: 1 -> 3 -> 4 -> 2 -> 5 -> null, m = 2, n = 3 Step2: 1 -> 4 -> 3 -> 2 -> 5 -> null, m = 2, n = 2 (Output)
把 mNode 插到 nNode 的后面，直到 mNode = nNode
TimeL O(n), Space: O(1)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode mNode = head;
ListNode preM = dummy;
ListNode nNode = head;
for (int i = 1; i < m; i++) {
preM = mNode;
mNode = mNode.next;
}
for (int j = 1; j < n; j++) {
nNode = nNode.next;
}
while (mNode != nNode) {
preM.next = mNode.next;
mNode.next = nNode.next;
nNode.next = mNode;
mNode = preM.next;
}
return dummy.next;
}
}