recursion - Combine two lists into one list Racket

Question

I have a question:

I have two list of numbers for example (list1 3 6 7) and (list2 1 6 4 7). Now I have to combine both into (list3 1 3 4). So 6 and 7 are both in list1 and list2. List3 contains all numbers which occur only once. I hope u get what i mean if not just ask me :s! Here my start:

(define (diff list1 list2)
  (cond
    [(empty? list1) list2] ;; If list1 was empty return directly list2
    [(empty? list2) list1] ;; If list2 was empty return directly list1
    [else
      (???

I know that I have to compare first list1 with every number in list2 and then recursiv again. But how do I programm it?

Answer 1

Here's a different, hopefully less-tricky, implementation. (It's O(n), but it requires both of the incoming lists to be sorted; in comparison, óscar's implementation does not required sorted lists, but it's O(n2).)

(define (diff lhs rhs)
  (let loop ((result '())
             (lhs lhs)
             (rhs rhs))
    (cond ((null? lhs) (append-reverse result rhs))
          ((null? rhs) (append-reverse result lhs))
          (else (let ((a (car lhs))
                      (b (car rhs)))
                  (cond ((< a b) (loop (cons a result) (cdr lhs) rhs))
                        ((< b a) (loop (cons b result) lhs (cdr rhs)))
                        (else (loop result (cdr lhs) (cdr rhs)))))))))

Example:

> (diff '(3 6 7) '(1 4 6 7))
(1 3 4)

append-reverse is from SRFI 1, so in Racket you have to (require srfi/1).