吐槽一下 今日头条的面试

确实是对的。
看起来面试官希望的是非递归的实现。估计当时没看懂。

对的吧，面试官说哪不对了？

其实这种应用用递归不是很合适。
当然这个面试官自己都弄不明白我觉得……

为什么我看到今日头条就想黑一下呢

《震惊，面试官居然看不懂递归排序，全世界的程序员都哭了》

你不起个这种标题，过的了技术面，也过不了 HR 面。

PS ：我感觉面试官当时脑子里有别的事，一时懵逼了，之后也是去干别的事了。

面试官说你不按常理出牌，我只背了迭代实现，你写个递归，我。。。

呵呵，当年面试小米我也写了个二分查找的递归，然后也面试官说不对。。。

坐等面试官

靠!
不就是工作久了忘了吗？
你小子至于拿到这来让我丢人现眼吗 ：）

面试的时候切忌和面试官争论 毕竟你的目的是拿到 OFFER 你对了有什么用？
高风亮节的人真的已经不多了

楼上是当事人现身说法？

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

def reverse(head):
if head == None:
return head
ret = reverseImpl(head)
head.next = None
return ret

不会 Python ，写成这样是不是对的呀？

@eamon666 你说得对。面试的过程还是很友好平和的。没有争论。

面试为啥要写递归，如果他不懂他就不会觉得你正确，如果他不觉得你正确你就有可能拿不到 offer 。。。

当面写代码其实对面试官压力更大。。。

这帖应该是今日头条

@dogfeet 两个版本 都有问题

这种递归栈太深了

我很少写递归的原因是，我写程序都会下意识的在脑子里面跑一遍。

如果写递归，我感觉我脑子就如同 stackoverflow 了一样难受。

所以我很少写，要写递归都是要下意识的告诉自己不要把这个程序放到脑子里面跑，不然就是炸裂一般的痛苦。

@Mirana 的确，最好还是要写循环迭代。当时觉得写循环更容易出错，所以选择写递归更简洁明了。

@davinci 不是 2 个版本哟，是一个。本意是， head == None 只需要第一次判断一次， head.nex = None 只需要最后递归完后原先的头节点执行一次。中间递归的过程中可以省略这 2 步。所以 reverse 调用的 reverseImpl 。

不过可能有问题吧，没装 py 环境没试 :(

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

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

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

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

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

@airqj 今日头条面试官？

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

会不会这样更好一点..

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

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

@tiancaiamao 完全同意。

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

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

补充一个 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;
}

```

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

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

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

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

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

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

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

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

然后我用数学归纳法简要地证明了一下这个算法的正确性

我比较好奇，帖主是如何用数学归纳法来证明算法的正确性的。算法没问题，

@davinci 如果只有数十个节点就是没有问题的，规模小了性能问题可以忽略。

@000wangxinyu000 时间复杂度 O(n)空间复杂度 O （ n ），算法本身没啥问题

@wshcdr 假设链表长度为 k 时，算法正确。根据该算法易证长度为 k+1 时算法依然正确。
当长度为 1 时，算法显然正确。所以为 2 时也正确，为 3 时也正确。。。为 n 时也正确 n 为任意正整数

震惊 。。。居然有人用 Python 写递归， scheme 看了会沉默， haskell 看了会流泪。。。

坐等：《我就是面试楼主的面试官，当时有事……》

个人认为公司不应该随便派人面试。面试官需要的技能比面试者高很多。一不小心就会这样了。。。

特意画图研究了下

1->2

1->2
↑---↓

1 2
↑---↓

666 ，感谢楼主让我这个菜鸟学到了逆置列表的新姿势ε=ε=ε=┏(ロ;)┛

@pwcong 哈哈 楼主也是菜鸟

@Shura 666

没看上你呗，招人除了技术能力过硬，最主要的还是喜欢对方

弱弱问一句，是不是只要
if (head.next == null)
return head;

就可以了? 感觉 head.next == null 会在 head == null 前出现，　 head == null 没用到啊？

楼上说对啦~~

@diangdiang
@superleexpert 要考虑到直接传入空链表的情况

表示上周末刚去头条面试，前后聊了 4 个人 8 个多小时，体验很不错。。。

再看楼主，怎么感觉 =.=
我感觉这个面试官要被查水表了。。。

@davinci 楼上的楼上

@luckymore0520 面试官被查水表不大可能吧。这也不是我的本意。我已经有其它公司的 offer 了，就是纯粹吐槽一下。感觉那天表现也不大好，即使面试官秒懂了我的思路，也不是稳拿 offer 。另外聊了 8 个多小时这么久感觉好夸张。。。

head.next.next = head

这块改一下就好了，改成下面这样。

nexthead = head.next
nexthead.next = head

不过招人就是这样，包括很多事情都是这样的，做了正确的事，其实不一定会得到正确的结果

这不就是 leetcode 上的题目么

@lytofb 这样一改 我反倒觉得更不直观了。。。

"把链表逆置"这种操作就跟"把汽车翻过来"一样
看起来好像很牛逼的样子,实际上没什么鸟用..

没毛病

@nagato ?

首先..我觉得链表逆序其实没啥好考的...其次我觉得 lz 写的是对的.... 虽然 head.next.next = head 这里不好理解。但理解了就很清晰了。面试官有点蠢..... 不过面试确实是运气的成分更大。

大概是你的变量名没有叫 amazing ！！！、 shocking ！！！

@a1310747 应该是的

@davinci 螺旋稳

面试官没看懂，可以要求跑几个 test case 。或者手动模拟一遍。感觉楼主被面试官坑了

面试官不懂估计懵逼了

楼主是校招内推吗？

怎么觉得这种递归下去的调用栈，比直接复制个新链表的开销还要大。。哪位大神给我讲讲内存开销呗？

个人感觉用 stack 简单清晰明了，考官可能想看看你是不是足够了解 stack ， queue 的特性？

def reverse(node):
stack = []
while node != None:
stack.append(node)
node = node.next
head = stack.pop()
last = head
while len(stack) > 0:
last.next = stack.pop()
last = last.next
last.next = None
return head

很少写 python ，我猜是对的

这个递归第一次看确实有点绕，但也不至于跑了 case 都看不懂。

不会贴代码。。。。。
def reverse(node):
stack = []

while node != None:
stack.append(node)
node = node.next
//end of while

head = stack.pop()
last = head

while len(stack) > 0:
last.next = stack.pop()
last = last.next
last.next = None
//end of while

return head

听说今日头条的面试是国内大厂里平均最难的…看了这个帖子我只是觉得这个面试官没连刷过 leetcode ，链表逆置用递归在面试题里是很常见的考法。

@CloudnuY 那变量名用 exciting 、 naive 、 simple 会不会更容易过？

大概三年前去面过一次头条，一面搞了两个小时，还是周六，能看出面试官还是挺不错的，因为下午直接接了前东家的 offer ，就没有再去二面。
两年前从前东家离职时直接又给原来的面试官发了简历，又去面了一次。笔试同样是链表翻转，我用 C++ 写的，结果新面试官直接说不会 C++，当时就有种“卧槽，这都行？”的感受，具体细节记不清了，但是只记得对面试官印象极差，一是把控不了整个面试过程，二是技术水平极差，就是一个个子不算高，稍微有点胖的哥们，年龄不大，应该工作没几年。还有最受不了的是二面的时间间隔，没有任何人告诉我需要等多长时间，我印象中去门口前台问了三四次需要多长时间，每次间隔应该都是半小时左右的，然后二面面试官才过来。上来就牛逼哄哄的说你原来做过阅读是吧，阅读排版具体是怎么做的？剩下的其他问题都忘了，唯一记得的就是没有问任何 Android 相关的东西。
应该是头条人太多了，所以也良莠不齐，自那以后再也没去面过头条，以后也不会再去了。

中肯的说，你确定你挂在了这道题上？

算法没毛病，给出归纳法证明更是加分项。

很多面试官心里想得不是面试你这个人，而是百般刁难你并以此展示自己的牛逼。如果遇到这种面试官，而你又让他吃相太难看，那你肯定挂了。

面试是一个偶然性相当大的事情，要看开啊。

看来面试官是个不懂装懂的傻 x

大厂么

今日头条算大厂，虽然我没用过

前段时间，我也面过今日头条。确实能感觉到面试官的水平没有那么好。

楼主最后去哪了？

我正好想问个问题， 关于面试的题目， 大家通常会优先用递归还是迭代啊？ 我现在用递归总觉得心里有点障碍，总担心面试官会说空间上效率不够高，让我再用迭代写一次。