Total Accepted: 59422 Total Submissions: 213019 Difficulty: Medium

 

Sort a linked list using insertion sort.

 

 

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* insertionSortList(ListNode* head) {        if(head==NULL || head->next==NULL){            return head;        }        ListNode* cur = head->next,*cur_pre=head,*cur_next=NULL;        while(cur){            cur_next = cur->next;                        /* 当前值小于前驱值，该节点需要重新调整 */            if(cur->val < cur_pre->val){                ListNode* insert_node_pre = NULL,*insert_node=head;                while(cur->val > insert_node->val){                    insert_node_pre = insert_node;                    insert_node = insert_node->next;                }                insert_node_pre ? insert_node_pre->next = cur : head = cur;                cur->next = insert_node;                cur_pre->next = cur_next;            }else{                cur_pre = cur;            }                        cur = cur_next;        }        return head;    }};

Next challenges: