如何反转一个链表？

「如何反转一个链表？」是一个在面试中被问滥的问题。我参与的面试中偶尔也有我们自己的面试官问。如果你去别的公司面试被问到这个问题，要是给出的答案是（以 Python 为例）：

def reverse(l):
  l.reverse()
  return l

或者是：

def reverse(l):
  return l[::-1]

肯定会被拒掉。面试官所预期的是你自己定义节点，再定义链表：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    # 以下略，问 ChatGPT 就可以了。

不过既然是个被问滥的问题，如果遇到不妨尽量给出一个面试官没见过的答案。比如，构造链表：

def cons(h, t):
    return lambda f: f(h, t)

取头：

def car(l):
    return l(lambda h, _: h)

取尾：

def cdr(l):
    return l(lambda _, t: t)

反转：

def reverse(l):
    rev = lambda l, r: rev(cdr(l), cons(car(l), r)) if l else r
    return rev(l, None)

以上就是完整答案。为了展示方便写个打印链表的函数：

def printl(l):
    toStr = lambda l: str(car(l)) + ' ' + toStr(cdr(l)) if l else ''
    print('(', toStr(l),')')

写个例子试一下：

l = cons(1, cons(2, cons(3, cons(4, None))))
printl(l)
printl(reverse(l))

输出是：

这应该是自己构造链表的最短答案了，但是有一定风险被面试官以奇怪的理由据掉。如果你是面试官，又想问这道题，就得了解各种实现方式，避免把不该拒的人拒了。🙃

推荐订阅源

0x01 byte