Java iterative and recursive solutions.
    \n    // iteratively\n    public ListNode insertionSortList(ListNode head) {\n        if (head == null || head.next == null) {\n            return head;\n  
        \n    // iteratively\n    public ListNode insertionSortList(ListNode head) {\n        if (head == null || head.next == null) {\n            return head;\n        }\n        ListNode p, dummy = new ListNode(0), node = head;\n        dummy.next = head;\n        while (node.next != null) {\n            if (node.val > node.next.val) {\n                p = dummy;\n                while (p.next != null && p.next.val < node.next.val) {\n                    p = p.next;\n                }\n                ListNode nxt = node.next.next;\n                node.next.next = p.next;\n                p.next = node.next;\n                node.next = nxt;\n            } else {  // already sorted\n                node = node.next;\n            }\n        }\n        return dummy.next;\n    }\n    \n    // recursively\n    public ListNode insertionSortList1(ListNode head) {\n        if (head == null || head.next == null) {\n            return head;\n        }\n        ListNode p = insertionSortList(head.next);\n        if (head.val <= p.val) {  // already sorted\n            head.next = p;\n            return head;\n        }\n        ListNode ret = p;\n        while (p.next != null && p.next.val < head.val) {\n            p = p.next;\n        }\n        head.next = p.next;\n        p.next = head;\n        return ret;\n    }
['Recursion', 'Iterator', 'Java']