class Solution {public: ListNode *insertionSortList(ListNode *head) { if (head == NULL) return NULL; ListNode* sorted_head = head; ListNode* unsorted_head = head->next; head->next = NULL; ListNode* cur = unsorted_head; while (cur != NULL) { unsorted_head = cur->next; cur->next = NULL; sorted_head = insertNode(sorted_head, cur); cur = unsorted_head; } return sorted_head; } ListNode* insertNode(ListNode* list, ListNode* node) { if (list == NULL && node == NULL) return NULL; if (node == NULL) return list; if (list == NULL) return node; ListNode* cur = list; ListNode* pre = NULL; while (cur != NULL && cur->val < node->val) { pre = cur; cur = cur->next; } if (pre == NULL) { node->next = list; return node; } else { node->next = pre->next; pre->next = node; return list; } }}; 感觉很简单，写起来又是这错那错
第二轮顺一些，先在纸上写好
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) { return NULL; } ListNode* sorted = head; ListNode* cur = head->next; // must after last line head->next = NULL; while (cur != NULL) { ListNode* next = cur->next; cur->next = NULL; sorted = insertNode(sorted, cur); cur = next; } ListNode* pre = NULL; return sorted; } ListNode *insertNode(ListNode* head, ListNode* node) { if (head == NULL) { return node; } if (node == NULL) { return head; } ListNode* cur = head; ListNode* pre = NULL; while (cur != NULL && cur->val < node->val) { pre = cur; cur = cur->next; } node->next = cur; if (pre == NULL) { return node; } else { pre->next = node; return head; } }}; 再来一发Python版本的，没有用python专用语法，比cpp慢了30倍
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = Noneclass Solution: # @param head, a ListNode # @return a ListNode def insertionSortList(self, head): if head is None: return None cur = head.next sorted = head sorted.next = None while cur is not None: next = cur.next cur.next = None sorted = self.insertNode(sorted, cur) cur = next return sorted def insertNode(self, head, node): if head is None: return node if node is None: return head cur = head pre = None while (cur is not None and cur.val < node.val): pre = cur cur = cur.next node.next = cur if pre is None: return node else: pre.next = node return head
再来：
/** * 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) { ListNode* list2 = NULL; ListNode* curr = head; while (curr != NULL) { ListNode* next = curr->next; list2 = insertion(list2, curr); curr = next; } return list2; } ListNode* insertion(ListNode* list, ListNode* node) { ListNode* head = list; ListNode* prev = NULL; while (list != NULL && node->val > list->val) { prev = list; list = list->next; } if (prev == NULL) { node->next = list; head = node; } else { node->next = prev->next; prev->next = node; } return head; }};