今天面试一个远程实习，国外做旅游的。沾一点 web3。
前面无非是那一套，然后最后肯定是一个经典的算法环节，给的是白板编程环境。连代码提示都没有，说实话，还好是写这道经典题，不然有些库函数写不出来还是有点尴尬的。
我也是用递归来写的，不过是我自己想的尾递归，不是网上流传很广的先递归进去的那种版本。所以之后就还和面试官讨论了一下，显然他熟悉的是那一种递归。
最后 battle 的结果是他认同了我的做法，毕竟我平时也是在 VSCode
中验证过的嘛。
贴一下我的思路。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode res = recurse(head, head.next);
head.next = null;
return res;
}
private ListNode recurse(ListNode cur, ListNode next) {
if (next == null) {
return cur;
}
ListNode tmp = next.next;
next.next = cur;
return recurse(next, tmp);
}
public static void main(String[] args) {
var solu = new Solution();
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
var res = solu.reverseList(head);
while (res != null) {
System.out.println(res.val);
res = res.next;
}
}
}
|
当然，最简单的方法肯定是直接模拟。直接上两个指针，不过，如果对递归比较熟悉的话，写这个递归的版本呢肯定是要更加快一点的。