吐槽一下 今日头条的面试

[davinci]

上周去今日头条面试。其中一道算法题的预处理步骤需要用到链表逆置。我写了一个递归函数。

def reverse(head):
    if head==None or head.next==None:
        return head
    result = reverse(head.next)
    head.next.next = head
    head.next = None
    return result

结果面试官看了几分钟，没看懂觉得有问题。然后我用数学归纳法简要地证明了一下这个算法的正确性，他想了几分钟还是觉得有问题，然后我又举了一两个简单例子展示该算法的运行过程，他看了一会儿想了一会儿还是觉得不对劲。末了，他叫我在这等一会，便抱着电脑出去了。我在屋子里等了半天也不见人影，大概过了有半小时，我走出面试房间，看到他，他说今天就面到这了。想想也是有些无语。

[eamon666]

@zer 你这个出现了“幻读”了 我的 LS 才是你该回复的呀 233

[x86]

@coderluan 《震惊，某程序员手写递归排序，男的看了沉默，女的看了流泪》

[jmc891205]

说句题外话 我觉得出 Python 面试题的时候应该尽量不要涉及链表
Python 对于任何链表适合解决的问题 都有其他更方便的数据结构可以用

[jmc891205]

@x86 楼主写的不是排序啊哈哈 UC 震惊部拒绝了你

[leyle]

震惊！今日头条招人黑幕，技术面试官竟然做出如此事情。。。

[davinci]

@dogfeet 这样写代码量过大。有种简单问题复杂化的感觉。脑补了一下，应该是对的。

[hornets]

@airqj 今日头条面试官？

[timle1029]

@dogfeet
def reverse(head):
pre = None
while head is not None:
next = head.next
head.next = pre
pre = head
head = next
return pre

会不会这样更好一点..

[mringg]

如果只是实现功能，递归毫无问题吧。
ps.话说楼上怎么有的扯到排序了

[tiancaiamao]

@dbdd 不不不，当面写代码还是面试者压力大一些，心态不一样。

[davinci]

@tiancaiamao 完全同意。

[uuweZhou]

这种面试官...水平会不会太次

单链表逆序的递归实现这种比较基础的题都...

补充一个 java 实现:

```java

public static Node reverse(Node head){

if (head==null||head.getNext()==null) {
return head;
}

Node reversedHead=reverse(head.getNext());

head.getNext().setNext(head);

head.setNext(null);

return reversedHead;
}

public static Node reverse1(Node head){

if (head==null) {
return head;
}

Node pre=head;

Node cur=head.getNext();

Node tem;

while(cur!=null){

tem=cur.getNext();

cur.setNext(pre);

pre=cur;
cur=tem;
}

head.setNext(null);
return pre;
}

```

[lekai63]

非程序员。。看了下这代码。。感觉跟那个解汉诺塔的算法一样~~

[lgh]

为什么一直没人说 == None 这个判断，不是应该用 is None 么？

[Anybfans]

@lgh #34 is None 感觉要快一点 其他两者没区别吧

[falcon05]

只有我觉得他出去是找个 case 运行了一下代码吗？

[000wangxinyu000]

这种做法是不是存在两个问题：
1 ）如上面某位说的，栈递归太深了。递归次数多了执行的时候会报错。
2 ）性能问题：你这种做法相当于，每次递归在函数栈上申请了一个临时变量，用这个临时变量指向当前递归的链表上的节点。等递归一个一个退栈的时候，通过索引这些临时变量把链表反向串起来。这种做法内存和时间的开销是不是比较大。

[linbiaye]

@000wangxinyu000 说得对，性能都是其次，主要问题是链表长了这个程序就得跪。

[linbiaye]

@davinci 楼主没有考虑输入规模。

[davinci]

@linbiaye
@000wangxinyu000 在那个问题背景下 链表长度最多只有几十个节点 如果从性能考虑 这种情况下 差距应该不大吧