子涵算法第十四天

92. 反转链表 II

原地法

class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for(int i = 0;i<left-1;i++){
pre = pre.next;
}
ListNode cur = pre.next;
for(int i = 0;i<right-left;i++){
ListNode move = cur.next;
cur.next = move.next;
move.next = pre.next;
pre.next = move;
}
return dummy.next;
}
}

时间复杂度：O(N)

空间复杂度：O(1)

25. K 个一组翻转链表

原地法：

class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null || k==1){
return head;
}
//虚拟节点保证head也可以翻转
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
while(true){
//检查还够不够k个节点翻转
ListNode check = pre;
for(int i = 0;i<k;i++){
check = check.next;
if(check == null){
return dummy.next;
}
}
ListNode cur = pre.next;
for(int j = 0;j<k-1;j++){
ListNode move = cur.next;
cur.next = move.next;
move.next = pre.next;
pre.next = move;
}
pre = cur;
}
}
}

时间复杂度：O(N)

空间复杂度：O(1)

总结：

1.原地法在应用链表翻转问题时很好用，核心就是pre定，cur根据pre定，move根据cur定，通过next关系进行翻转