LeetCode 的 C++ 实现（四）插入排序对链表进行排序的各类实现

链表进行排序的各类实现"/>

LeetCode 的 C++ 实现（四）插入排序对链表进行排序的各类实现

题目

使用插入排序对链表进行排序。
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 dummyhead(0); //空指针大法，用来返回和遍历新链表ListNode* cur = head;//ListNode* p = &dummyhead;while(cur){ListNode* cachenext = cur->next;//用来缓存下个节点，下下一轮遍历的头结点ListNode* p = &dummyhead;while( p->next != nullptr && p->next->val < cur->val){p = p->next;}cur->next = p->next;//断开原链表p->next = cur;//插入新链表cur = cachenext;}return dummyhead.next;}
};

递归

网上看到一个很巧妙的方法，在插入的基础上做的改进，每轮递归只插入当前头结点，剩下的交给递归

class Solution {
public:ListNode *insertionSortList(ListNode *head) {if(!head || !head->next) return head;ListNode dummyHead(0), *p;dummyHead.next = insertionSortList(head->next);p = &dummyHead;while(p && p->next && head->val > p->next->val){p = p->next;}head->next = p->next;p->next = head;return dummyHead.next;}
};