My accepted C++ solution


  • 0
    V

    Because this is a singly-linked list, so I use a vector to store prevous node pointer.

    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
            if (!head) { return nullptr; }
            std::vector<ListNode*> prevs;
            prevs.push_back(head);
            ListNode* cur = head->next;
            while (cur) {
              ListNode* cur_tmp = cur;
              for (int i = (int)prevs.size() - 1; i >= 0; --i) {
                ListNode* node = prevs[i];
                if (node->val <= cur->val) { break; }
                auto tmp = node->val;
                node->val = cur->val;
                cur->val = tmp;
                cur = node;
              }
              prevs.push_back(cur_tmp);
              cur = cur_tmp->next;
            }
            return head;
        }
    };

Log in to reply
 

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