经典永流传之反转链表

今天面试一个远程实习，国外做旅游的。沾一点 web3。

前面无非是那一套，然后最后肯定是一个经典的算法环节，给的是白板编程环境。连代码提示都没有，说实话，还好是写这道经典题，不然有些库函数写不出来还是有点尴尬的。

我也是用递归来写的，不过是我自己想的尾递归，不是网上流传很广的先递归进去的那种版本。所以之后就还和面试官讨论了一下，显然他熟悉的是那一种递归。

最后 battle 的结果是他认同了我的做法，毕竟我平时也是在 VSCode 中验证过的嘛。

贴一下我的思路。

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;
        }
    }
}

当然，最简单的方法肯定是直接模拟。直接上两个指针，不过，如果对递归比较熟悉的话，写这个递归的版本呢肯定是要更加快一点的。