Ways to reverse one directional list

Table of Contents

• 1 How I get this question?
• 2 So the answer is?
• 3 What did I learn from this question?

1 How I get this question?

I attended a job interview again yesterday, the interviewer asked me some many questions including object-oriented software design, data structure, and algorithms. The written examination which is android SDK related should be my strong points one years ago, but Now I forgot most of the terms. So sucks huh! I list the following topics from my memory after the lasting 3 hours job interview.

1. Plugin design patterns: Cons and Pros, How eclipse project leading this tide.
2. Dynamic Programming language and OOP
3. Lisp language, Functional programming, and Recursion
4. Algorithms

Most of the questions enlightening me so much, this interviewer is obviously a good engineer. 

wow… Great job.

Now, come back the topic. How to reverse a one-directional list? This question was given when we discuss the functional programming.

2 So the answer is?

There are two ways to reverse a one-directional list, the recursion version, and the stack version.

The interviewer gives me a hint of the recursion version. And here is the elisp implementation.

(defun get-symbols (lst)
  (when lst
    (if (atom lst) (list lst)
      (append (get-symbols (car lst))
              (get-symbols (cdr lst))))))

(defun reverse-list (a)
  (let ((b (cdr a))
        )
    (if b
        (append (get-symbols (reverse-list b)) (get-symbols (car a)))
      a)
    ))

;; test cases
(reverse-list  '(1 2 3 4 5 6 7 8))
(reverse-list '(1))

(get-symbols '(1 2 3 (5 6)))

I upload the C version of the source code into Github. I wish you enjoy it.

3 What did I learn from this question?

Recursion is to allow a function to call itself within the program text. And it is the soul of Functional programming. It is the most familiar algorithm to solve the one-directional list reverse question. But how to solve this question in none functional programming featured languages, the replacer is to use the stack. In general, you can take the place of the recursion algorithm with stack solution, and vice versa.