链表进行排序的各类实现"/>
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;}
};
更多推荐
LeetCode 的 C++ 实现(四)插入排序对链表进行排序的各类实现
发布评论