[排序][链表]Leetcode147 对链表进行插入排序

思路：

插入算法的思想很简单，此题比较为链表数据类型，方便的是不用一个一个的向后移动元素，但是找到应该插入的位置相对麻烦，因为链表只有next指针，无法快速定位要插入的位置。在链表前面插入一个空指针，指向头节点，方便后续的访问和减少判断。

class Solution {

public:

    ListNode* insertionSortList(ListNode* head) {

        const int inf = 0x3f3f3f3f;

        if(head == NULL) return NULL;

        if(head->next == NULL) return head;

        //构建一个空指针指向开头

        ListNode *headNULL = new ListNode(inf);

        headNULL -> next = head;

        ListNode *cur = head->next;

        head -> next = NULL;

        while(cur !=NULL){

            ListNode *p = headNULL;

            while(p->next != NULL && p->next->val < cur->val){ //当找到第一个大于当前值的节点时，退出循环

                p = p->next;

            }

            //此时p->next 既是第一个大于当前值的节点，p指向应插入位置的前一个节点，即要在p和p->next之间插入当前值

            ListNode *tmp = cur->next;

            cur -> next = p->next;

            p -> next = cur;

            cur = tmp;

        }

    //返回首节点

    return headNULL->next;

    }

};

巴特西

[排序][链表]Leetcode147 对链表进行插入排序

最新文章

热门文章