Reverse List Range
翻转链表中第m个节点到第n个节点的部分
样例
给出链表1->2->3->4->5->null, m = 2 和n = 4,返回1->4->3->2->5->null
注意
m,n满足1 ≤ m ≤ n ≤ 链表长度
挑战
在原地一次翻转完成
Solution
先找到要翻转的起点节点,然后翻转
Complexity
时间复杂度 O(n),空间复杂度 O(1)
Code
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param ListNode head is the head of the linked list
* @oaram m and n
* @return: The head of the reversed ListNode
*/
public ListNode reverseBetween(ListNode head, int m , int n) {
if (m >= n || head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
for (int i = 1; i < m; i++) {
if (head == null) {
return null;
}
head = head.next;
}
ListNode premNode = head;
ListNode mNode = head.next;
ListNode nNode = mNode, postnNode = mNode.next;
for (int i = m; i < n; i++) {
if (postnNode == null) {
return null;
}
ListNode temp = postnNode.next;
postnNode.next = nNode;
nNode = postnNode;
postnNode = temp;
}
mNode.next = postnNode;
premNode.next = nNode;
return dummy.next;
}
}