如何在Scheme中实现无重复的merge合并函数？

嘿，我来帮你搞定这个无重复merge的需求！你的原代码问题出在没有处理两个列表首元素相等的情况，导致相等的元素会被分别添加到结果里。咱们只需要在cond里加一个分支，专门处理元素相等的场景就行。

修改后的代码 #

(define (merge lst1 lst2)
  (cond
    ((null? lst1) lst2)          ; 第一个列表空了，直接返回第二个
    ((null? lst2) lst1)          ; 第二个列表空了，直接返回第一个
    ((= (car lst1) (car lst2))   ; 遇到相等元素，只保留一个，同时递归处理两个列表的剩余部分
     (cons (car lst1) (merge (cdr lst1) (cdr lst2))))
    ((> (car lst1) (car lst2))   ; 第一个元素更大，先取第二个列表的元素
     (cons (car lst2) (merge lst1 (cdr lst2))))
    (else                        ; 第二个元素更大，先取第一个列表的元素
     (cons (car lst1) (merge (cdr lst1) lst2)))))

测试验证 #

调用你给的例子：

(merge '(1 2 8) '(2 5 6))

会返回 '(1 2 5 6 8)，完美符合你的要求！

注意事项 #

这个函数的前提是输入的两个列表都是已经按升序排好序的，就像你例子里的那样。如果输入的列表是无序的，这个merge函数的结果也会是无序的，而且去重逻辑也可能失效哦。

内容的提问来源于stack exchange，提问作者Shmuel Niraev