插入排序 - 链接列表 - 递归

Question

我一直在尝试编写一个程序来使用插入排序对链接列表进行排序，并且我找到的解决方案以迭代的方式执行，我们如何编写递归算法？

ps。这不是一个分配问题。

Answer 1

To insert a node n to a list L: 
    If L is empty, return n 
    Split L into L0 (the head, first item in L) and LR (the rest) 
    If n.data < L0.data then insert n at the head of L and return L 
    insert n into LR and return L