My c++ solution


  • 0
    T

    class Solution {
    public:
    ListNode *insertionSortList(ListNode *head) {
    if (!head) return head;
    ListNode vitual_head(0);
    vitual_head.next = head;
    int sortedCnt = 1;
    ListNode * cur_pre = head;
    ListNode * cur = head->next;
    while (cur)
    {
    ListNode * pre = &vitual_head;
    ListNode * iter = pre->next;
    bool inserted = false;
    for (int i = 0; i < sortedCnt && iter; ++i, pre = iter, iter = iter->next)
    {
    if (cur->val < iter->val)
    {
    //delete cur
    cur_pre->next = cur->next;
    //insert before iter
    pre->next = cur;
    cur->next = iter;
    inserted = true;
    break;
    }
    }
    if (!inserted)
    {
    cur_pre = cur;
    }
    ++sortedCnt;
    cur = cur_pre->next;
    }// end while(cur)
    return vitual_head.next;
    }
    };


Log in to reply
 

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