记录:一道单链表逆置题(智商真的不够用,没救了)
大佬们发来这样一道面试题,三行三句代码,完成单链表逆置功能。
一开始我的想法,是在reverse(Node head)这个方法里递归,在后一个reverse方法里完成具体逆置操作。
于是在后一个reverse方法里,我是这么写的:
Node newNode = next.node;
next.node = cur;
这样就完成了单个节点的逆置
但是在第一个reverse方法里,反复试了好几次递归,都有问题,一次栈溢出(说明无限递归了),一次空指针,一次没有逆置成功。
于是我开始怀疑是不是我的递归写错了地方。
当时比较懒,没有顺手拿张纸画一画,靠脑袋硬想。后来大佬给了个提醒,然后重新写了一个解法,好用了,逆置成功。
代码如下:
public class Node {
public int value;
public Node next;
public Node(int value) {
this.value = value;
}
public static Node reverse(Node head) {
return reverse(null, head);
}
public static Node reverse(Node cur , Node next) {
if(next == null) {
return cur;
}
Node newNode = reverse(next,next.next);
next.next = cur;
return newNode;
}
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
n1.next = n2;
n2.next = n3;
n3.next = n4;
n4.next = n5;
reverse(n1);
System.out.println(n5.next.value);
}
}
所以,第一个reverse方法只是一个幌子,精华还是在第二个reverse方法中。
先递归把next节点后面的节点全部逆置完成,然后把next节点指向cur节点即可。
其实挺简单的一个理,写好之后马上就明白怎么回事了。
但就是智商不够用,真的没救了。