Insertion Sort 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) {        ListNode *sortedHead = new ListNode(-1);        while(head != NULL)        {            //保存head位置            ListNode *temp = head->next;            ListNode *cur = sortedHead;            while(cur->next != NULL && cur->next->val < head->val)            {                cur = cur->next;            }            //插入            head->next = cur->next;            cur->next = head;            //恢复head            head = temp;        }        return sortedHead->next;    }};