2

如何反转一个链表？

 1 year ago
source link: https://1byte.io/how-to-reverse-a-linked-list/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

1 Byte

如何反转一个链表？

2023-05-17

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

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

订阅我的邮件列表以得到新文章通知：


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK