实现移除相邻重复元素函数：已有部分代码，寻求完整实现

你已经搭好了函数的基础框架，咱们把它补全，同时聊聊怎么让它更高效。

先来看基础的完整实现版本：

(define (remove-adjacent-duplicates ls)
  (if (null? ls)
      '()
      (let ((first (car ls)))
        (let loop ((known first) 
                   (rest (cdr ls)) 
                   (result (list first)))
          (cond
            ((null? rest) result)
            ((equal? known (car rest))
             ; 当前元素和上一个保留的元素重复，直接跳过
             (loop known (cdr rest) result))
            (else
             ; 当前元素是新的，加入结果并更新跟踪的元素
             (loop (car rest) 
                   (cdr rest) 
                   (append result (list (car rest))))))))))

代码逻辑拆解 #

1. 边界处理：如果输入是空列表，直接返回空，这是最基础的边界条件。
2. 循环初始化：对于非空列表，先取出第一个元素作为known（我们需要跟踪的上一个被保留的元素），初始结果列表result只包含这个首元素，rest则是列表剩余的部分。
3. 遍历判断：
   • 当rest为空时，说明遍历完成，直接返回结果列表。
   • 如果当前rest的首元素和known相等，说明是相邻重复元素，跳过它继续遍历剩下的部分。
   • 如果元素不重复，就把它加入结果列表，更新known为这个新元素，再继续遍历后续内容。

效率优化版 #

上面的版本用了append添加元素，但append每次都会遍历整个结果列表，长列表场景下效率偏低。我们可以改用cons（O(1)操作）把元素加到结果列表头部，最后再反转得到正确顺序：

(define (remove-adjacent-duplicates ls)
  (if (null? ls)
      '()
      (let ((first (car ls)))
        (let loop ((known first) 
                   (rest (cdr ls)) 
                   (result (list first)))
          (cond
            ((null? rest) (reverse result))
            ((equal? known (car rest))
             (loop known (cdr rest) result))
            (else
             (loop (car rest) 
                   (cdr rest) 
                   (cons (car rest) result))))))))

测试验证 #

你给出的测试用例都能正确运行：

(remove-adjacent-duplicates '(y a b b a d a b b a d o o)) ; 返回'(y a b a d a b a d o)
(remove-adjacent-duplicates '(yeah yeah yeah)) ; 返回'(yeah)

这个实现的核心是跟踪上一个被保留的元素，避免重复添加相邻的相同元素，逻辑清晰且高效。

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