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回答

liuyubobobo

2021-03-27

tmp = cur.next 报空指针异常,肯定是因为 cur 是 null,所以 cur.next 报异常。


==========


我测试了一下你的代码,在 1->2->3 这样一个只有三个节点的链表,k = 2 的情况下,就会报异常。用这个小数据用例,实际去运行你的程序,考单步跟踪的方式去看一下,你的程序的各个变量在这个过程中是怎么变化的?在哪里,程序的变量和你的想法不一致?是自己想错了?还是边界没考虑到?或者识别的原因?为什么自己之前的思考是有问题的。


这是学习算法乃至计算机的重要方法。而不是单纯地靠“想”。一定要动手去调,在这个过程中,才能对程序的运行认识的越来越深刻,才能逐渐做到用眼睛就能调 bug,甚至是写出来就没 bug。


进步就在这个过程中。你应该把 80% 的精力,用在调程序上,而不是编程序上。变出一个不能运行正确的程序框架是简单的,但把一个程序真正调试正确,才是最关键的。


继续加油!:)

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2638 学习 · 1091 问题

查看课程