[抄题]:
给你一个链表以及一个k,将这个链表从头指针开始每k个翻转一下。
链表元素个数不是k的倍数,最后剩余的不用翻转。
[思维问题]:
[一句话思路]:
// reverse head->n1->..->nk->next.. // to head->nk->..->n1->next.. // return n1 每k个转一次,再递归
[输入量]:空: 正常情况:特大:特小:程序里处理到的特殊情况:异常情况(不合法不合理的输入):
[画图]:
[一刷]:
- head = dummy,记住:head从第0位开始
if (head == null || k <= 1) {
return head; k == 1时,返回原来的head不转就行,不是返回null
}- head.next要新存节点,否则会报错,递归还不能debug
- reverseNextK是需要循环调用的,是否够k个数的判断在其中完成。
n1.next = curt;指针先连接
head.next = prev;本体后连接,防止破坏指针- next.next为空时退出,特殊情况应该是退出
[总结]:
head = dummy,记住:从第0位开始
[复杂度]:Time complexity: O(n) Space complexity: O(1)
[英文数据结构,为什么不用别的数据结构]:
[其他解法]:
[Follow Up]:
[题目变变变]:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/ public class Solution {
/*
* @param head: a ListNode
* @param k: An integer
* @return: a ListNode
*/
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null || k <= 1) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy; while (head.next != null) {
head = reverseNextK(head,k);
} return dummy.next;
} //reverseNextK
private ListNode reverseNextK(ListNode head, int k) {
ListNode next = head;
for (int i = 0; i < k; i++) {
if (next.next == null) {
return next;
}
next = next.next;
}//whether next is enough ListNode prev = head;
ListNode n1 = head.next;
ListNode curt = n1;
for (int i = 0; i < k; i++) {
ListNode temp = curt.next;
curt.next = prev;
prev = curt;
curt = temp;
} n1.next = curt;
head.next = prev; return n1;
}
}