147. Insertion Sort List

Similar to "86. Partition List", don't forget to process a special case where no insertion is needed.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      dummy->next = head;  
14:      ListNode *head_prev = dummy;  
15:      while (head) {  
16:        ListNode *prev = dummy, *cur = dummy->next;  
17:        while (cur->val < head->val) {  
18:          prev = cur;  
19:          cur = cur->next;  
20:        }  
21:        if (cur == head) {
22:          head_prev = head;  
23:          head = head->next;  
24:        } else {  
25:          head_prev->next = head->next;  
26:          head->next = cur;  
27:          prev->next = head;  
28:          head = head_prev->next;  
29:        }  
30:      }  
31:      return dummy->next;  
32:    }  
33:  };  

Then code above only beats 24%, so it can be improved to beat 80%

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      ListNode *dummy = new ListNode(-1);  
13:      dummy->next = head;  
14:      ListNode *prev = dummy, *cur = head;  
15:      while (cur) {  
16:        if (cur->next && cur->next->val < cur->val) {  
17:          while (prev->next && prev->next->val < cur->next->val) {  
18:            prev = prev->next;  
19:          }  
20:          ListNode *tmp = cur->next->next;  
21:          cur->next->next = prev->next;  
22:          prev->next = cur->next;  
23:          cur->next = tmp;  
24:          prev = dummy;  
25:        } else {  
26:          cur = cur->next;  
27:        }  
28:      }  
29:      return dummy->next;  
30:    }  
31:  };  

When I revisited this problem, I had a more concise solution.

1:  /**  
2:   * Definition for singly-linked list.  
3:   * struct ListNode {  
4:   *   int val;  
5:   *   ListNode *next;  
6:   *   ListNode(int x) : val(x), next(NULL) {}  
7:   * };  
8:   */  
9:  class Solution {  
10:  public:  
11:    ListNode* insertionSortList(ListNode* head) {  
12:      if (head == NULL) return NULL;  
13:      ListNode *dummy = new ListNode(-1);  
14:      ListNode *cur = head->next;  
15:      dummy->next = head, head->next = NULL;  
16:      while (cur) {  
17:        ListNode *p = dummy, *q = dummy->next;  
18:        while (q && q->val < cur->val) { p = q; q = q->next; }  
19:        p->next = cur;  
20:        cur = cur->next;  
21:        p->next->next = q;  
22:      }  
23:      head = dummy->next;  
24:      delete dummy;  
25:      return head;  
26:    }  
27:  };