LeetCode – Refresh – Insertion Sort List

 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 || !head->next) return head;
13         ListNode *result = new ListNode(0);
14         ListNode *old = new ListNode(0);
15         old->next = head;
16         while (old->next) {
17             ListNode *tmp = old->next, *runner = result;
18             old->next = tmp->next;
19             while (runner) {
20                 if (!runner->next || tmp->val < runner->next->val) {
21                     tmp->next = runner->next;
22                     runner->next = tmp;
23                     break;
24                 }
25                 runner = runner->next;
26             }
27         }
28         return result->next;
29     }
30 };