反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
/**
* 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) {
int len = 0;
ListNode node = head;
ListNode fPre = null;
ListNode tPos = null;
while (node!=null){
len++;
fPre = (len == m-1) ? node : fPre;
tPos = (len == n+1) ? node : tPos;
node = node.next;
}
if(m < 1 || n > len)
return head;
node = fPre == null ? head : fPre.next;
ListNode node1 = node.next;
node.next = tPos;
ListNode next = null;
while (node1 != tPos){
next =node1.next;
node1.next = node;
node = node1;
node1 = next;
}
if(fPre != null){
fPre.next = node;
return head;
}
return node;
}
}
复杂度分析：
时间复杂度:O(N)
空间复杂度:O(N)
