如何反转一个链表?

「如何反转一个链表?」是一个在面试中被问滥的问题。我参与的面试中偶尔也有我们自己的面试官问。 如果你去别的公司面试被问到这个问题,要是给出的答案是(以 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))

输出是:

( 1 2 3 4  )
( 4 3 2 1  )

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


最新文章

评论

Loading comments ...