leetcode 25题 k个一组翻转链表
来源:1-1 什么是链表
mahsiaoko
2021-03-27 18:57:23
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode res=new ListNode(0);
res.next=head;
ListNode prev=res;
while(head!=null){
ListNode tail=prev;
for(int i=0;i<k;i++){
tail=tail.next;
if(tail==null){
return res.next;
}
}
ListNode nextPart=tail.next;
ListNode[] nodes=reverse(head,tail);
head=nodes[0];
tail=nodes[1];
tail.next=nextPart;
prev.next=head;
head=tail.next;
prev=tail;
}
return res.next;
}
// 1 2 3 4 ,5 -> 4 3 2 1 ,5
private ListNode[] reverse(ListNode head,ListNode tail){
ListNode prev=tail.next;
ListNode cur=head;
while(cur!=tail.next){
ListNode tmp=cur.next;
cur.next=prev;
prev=cur;
cur=tmp;
}
// while(prev!=tail){
// ListNode tmp=cur.next;
// cur.next=prev;
// prev=cur;
// cur=tmp;
// }
return new ListNode[]{tail,head};
}
}
老师,您好!
在reverse函数中的while判断,我不理解为什么prev!=tail就可以,但是cur!=tail.next就会报空指针异常,而我如果此时下面这样写 又会正常
ListNode prev=tail.next;
ListNode cur=head;
ListNode end=tail.next;
while(cur!=end){
ListNode tmp=cur.next;
cur.next=prev;
prev=cur;
cur=tmp;
}
这个空指针异常是发生在哪个节点 ?我有点想不明白
1回答
tmp = cur.next 报空指针异常,肯定是因为 cur 是 null,所以 cur.next 报异常。
==========
我测试了一下你的代码,在 1->2->3 这样一个只有三个节点的链表,k = 2 的情况下,就会报异常。用这个小数据用例,实际去运行你的程序,考单步跟踪的方式去看一下,你的程序的各个变量在这个过程中是怎么变化的?在哪里,程序的变量和你的想法不一致?是自己想错了?还是边界没考虑到?或者识别的原因?为什么自己之前的思考是有问题的。
这是学习算法乃至计算机的重要方法。而不是单纯地靠“想”。一定要动手去调,在这个过程中,才能对程序的运行认识的越来越深刻,才能逐渐做到用眼睛就能调 bug,甚至是写出来就没 bug。
进步就在这个过程中。你应该把 80% 的精力,用在调程序上,而不是编程序上。变出一个不能运行正确的程序框架是简单的,但把一个程序真正调试正确,才是最关键的。
继续加油!:)
相似问题