插入排序 - 鏈接列表 - 遞歸

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