首页 > 代码库 > 【LeetCode】Insertion Sort List

【LeetCode】Insertion Sort List

Insertion Sort List

Sort a linked list using insertion sort.

 

本题是插入排序的链表版本。

传统数组版本做法就是两重循环,第一重是遍历所有元素,第二重是遍历已排序部分进行插入。

链表版本类似,在遍历每个元素过程中,遍历已排序部分进行插入。

 

上代码,代码参考九章算法解题站。

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;    }};

 

【LeetCode】Insertion Sort List