My concise C++ solution


  • 0
    Z
    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            if (!head) return NULL;
            ListNode *newHead = new ListNode(head -> val);
            ListNode *cur1 = head;
            while (cur1 -> next) {
                cur1 = cur1 -> next;
                ListNode *cur2 = newHead;
                if (newHead -> val > cur1 -> val) {
                    ListNode *tmp = new ListNode(cur1 -> val);
                    tmp -> next = newHead;
                    newHead = tmp;
                    continue;
                }
                while (true) {
                    if (!cur2 -> next) {
                        cur2 -> next = new ListNode(cur1 -> val);
                        break;
                    }
                    if (cur2 -> next -> val >= cur1 -> val) {
                        ListNode *tmp = new ListNode(cur1 -> val);
                        tmp -> next = cur2 -> next;
                        cur2 -> next = tmp;
                        break;
                    } else cur2 = cur2 -> next;
                }
            }
            return newHead;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.