给定2个列表，如何生成第3个列表的输出，该列表的元素为L1和L2的交错集合？如果长度不均匀，则应插入零孔。在第二个注释中，我如何反转列表？我是LISP的新手，只是修改现有代码......我真的很想得到一个很好的解释，而不仅仅是代码。
首先，我猜你使用Common Lisp，因为它是Lisp课程中最常用的。所以，我的例子将在CL中。如果您使用Scheme，您将获得几乎相同的代码。如果是现代的Clojure，它将需要一些改变，通过一个想法将是相同的。
交错
要交错2个列表，您必须遍历它们，轮流收集元素。您可以使用循环语句或递归。我将使用递归，因为它具有更多的功能样式，并且可以在任何lisp中使用，而不仅仅是CL。另请注意，有一个名为tail recursion的功能，它允许您编写将被编译为循环的递归函数。 所以，我们函数的基础骨架将是：
(defun interleave (l1 l2)
??????
(interleave ?????))
要在递归函数中收集项目，您需要从每次调用中返回它们然后合在一起（对于尾部递归，您必须有一个参数，这将累积值）。所以，函数的结尾将是(cons current-value (interleave ????))。此外，您必须使用备用列表来相互接收元素。您可能有其他参数，但您也可以在递归调用中交换它们。所以，代码变成：
(defun interleave (l1 l2)
?????
(cons current-value (interleave l2 l1)))
任何递归必须在某处停止。在这种情况下，它必须在两个列表都为空（nil）时停止。这是一个条件（让它给它1号），还有一些条件： 2.如果要取的列表是空的，而另一个不是，我们必须取而代之。 3.如果两个列表都不为空，则将第一个元素作为当前值并继续它的尾部。
只有一个条件可以包含2个列表：要取自的列表不为空，第二个列表为空。但事实上我们并不关心这一点，可能会使用规则3前进。所以，代码（这是最后的代码）：
(defun interleave (l1 l2)
(cond ((and (eql l1 nil) (eql l2 nil)) nil) ;; rule #1
((eql l1 nil) (cons nil (interleave l2 l1))) ;; rule #2, current value is nil
(true (cons (first l1) (interleave l2 (rest l1)))))) ;; rule #3 in all other cases
相反
我将展示这个函数的两个实现：一个使用cond，另一个使用内置的reduce函数，这在实践中非常有用。
cond版本的第一种方法是通过递归调用遍历所有列表，然后返回，收集元素：
(defun reverse-1-1 (li)
(if (eql li nil)
nil
(append (reverse-1-1 (rest li))
(list (first li)))))
但这是非常低效的，因为append是O(n)，你必须传递n个元素，所以最终的复杂性是O（n ^ 2）。
为了减少它，你可以再使用一个函数参数（如果编译器允许的话，使其尾递归）：
(defun reverse-1-2 (li)
(reverse-aux li nil))
(defun reverse-aux (li accumulator)
(if (eql li nil)
accumulator
(reverse-aux (rest li) (cons (first li) accumulator))))
那是你在通过列表时使用另外一个参数来收集你的元素，然后只返回这个累加器。
还有一个有趣的选择。 Lisp具有非常强大的功能reduce（在其他功能语言中，它有时被称为fold，foldr，foldl或类似的东西）。你可以找到它的描述here，我只是举个例子：
(defun reverse-2 (li)
(reduce #'cons li :from-end t :initial-value nil))
:from-end告诉函数从最后遍历列表，并且：initial-value告诉我们使用nil作为第一个减少的参数。
注意：在某些实现中，使用选项:from-end true可以首先自动反转列表，因此如果您需要从头开始创建它或使用最有效的版本，请改用reverse-1-2。
在Common Lisp中：
(defun merge-lists (lst1 lst2)
(let ((m (max (length lst1) (length lst2))))
(flatten (mapcar (lambda (a b) (list a b))
(append-nulls lst1 m)
(append-nulls lst2 m)))))
例子：
(merge-lists '(1 2 3 4) '(5 6 7 8)) ;; => (1 5 2 6 3 7 4 8)
(merge-lists '(1 2 3 4) '(5 6 7)) ;; => (1 5 2 6 3 7 4 NULL)
(merge-lists '(1 2) '(5 6 7 8)) ;; => (1 5 2 6 NULL 7 NULL 8)
辅助函数flatten和append-nulls：
(defun flatten (tree)
(let ((result '()))
(labels ((scan (item)
(if (listp item)
(map nil #'scan item)
(push item result))))
(scan tree))
(nreverse result)))
(defun append-nulls (lst n)
(if (< (length lst) n)
(dotimes (i (- n (length lst)))
(setq lst (append lst (list 'null)))))
lst)
答案如下：
(defun interleave (l1 l2)
(cond ((and (eql l1 nil) (eql l2 nil)) nil) ;; rule #1
((eql l1 nil) (cons nil (interleave l2 l1))) ;; rule #2, current value is nil
(true (cons (first l1) (interleave l2 (rest l1)))))) ;; rule #3 in all other cases
如果你的一个列表比另一个更长，你会得到类似的东西（1 2 3 4 nil 5）。替换：（（eql l1 nil）（cons nil（interleave l2 l1）））
with :(（null l1）l2）
：P
Common Lisp中更惯用的解决方案示例：
(defun interleave (a b)
(flet ((nil-pad (list on-list)
(append list (make-list (max 0 (- (length on-list) (length list)))))))
(loop for x in (nil-pad a b)
for y in (nil-pad b a)
append (list x y))))