对链表进行插入排序

大家好,我是芒果,一名非科班的在校大学生。对C/C++、数据结构、Linux及MySql、算法等领域感兴趣,喜欢将所学知识写成博客记录下来。 希望该文章对你有所帮助！如果有错误请大佬们指正！共同学习交流

作者简介:

• CSDN C/C++领域新星创作者https://blog.csdn.net/chuxinchangcun?type=blog
• 掘金LV3用户 https://juejin.cn/user/1381426159953960
• 阿里云社区专家博主,星级博主,技术博主 https://developer.aliyun.com/profile/expert/5lkdbuggiiuhc
• 华为云云享专家 https://bbs.huaweicloud.com/community/myhomepage

题目要求

147. 对链表进行插入排序 - 力扣（LeetCode） (leetcode-cn.com)

主要思路：取第一个下来作为头（第一个认为是有序的），把后面的结点依次从前往后比较进行插入，保证是有序的

• 如果链表为空 或者 链表只有一个结点就不需要排序了，直接返回原来的头

• 把链表的头结点取下来作为新链表的头结点，并且把它的next置空，定义新链表的头指针为：sorthead

  

  ---

• 定义指针cur用于遍历要排序的链表，把cur指向的结点插入到新链表中，并且保持有序,初始化：cur = head->next，因为第一个结点都取下来当新链表的头了

• Case1：头插

  • 对应情况：cur->val <= sorthead->val

  • 方法：把cur指向的结点头插到sorthead链表中

  • if(cur->val <= sorthead -> val)
    {
        //头插
        cur->next = sorthead;//cur指向的结点头插到新链表
        sorthead = cur;//更新头指针
    }
    

    

• Case2 :中间插入

  • 对应情况：Case1的else情况
  • 方法：定义sortcur指针遍历链表找到插入到位置，为了方便链接，再定义一个sortprev(sortcur的前驱结点)，最初sortprev赋值为sorthead，sortcur赋值为sorthead->next，因为不是头插，所以从第二个结点开始往后比较
  • 利用sortcur遍历新链表，如果找到了cur->val <= sortcur->val 位置，则在sortcur的前面进行插入(插入到sortprev后面)
  • 否则进行迭代往后走，sortprev始终在sortcur的前一个位置
  • 插入后，要break跳出while循环
  • 如果直到sortcur为空了都没有找到位置插入 ->即为尾插情况
  • 

• Case3: 尾插

  • 对应情况：sortcur == NULL
  • 方法：把cur指向的结点，尾插到sortprev的后面，然后cur的next要记得置空(变成了新的尾)
  • 

• 然后cur迭代往后走，直到cur为空(把要排序的链表遍历完)

• 最后返回sorthead

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *nex t;
 * };
 */
​
typedef struct ListNode Node;
struct ListNode* insertionSortList(struct ListNode* head)
{
        //链表为空||链表只有一个结点就不用排序了
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
    //排序完成的链表的头结点 - sorthead
    Node* sortHead = head;//把要排序链表的第一个结点取下来
    sortHead->next = NULL;//并且把第一个结点的next置空
    Node* cur = head->next;//用于遍历要排序的链表
    //cur遍历要排序的链表
    while(cur)
    {
        //先保存cur的下一个结点
        Node* next = cur->next;
​
        //把cur插入到sortHead链表中，并且保持有序
        //case1:头插
        if(cur->val <= sortHead ->val)
        {
            //头插
            cur->next = sortHead;//cur指向的结点链接sorthead链表
            sortHead = cur;//更新头指针
        }
        else
        {
            //case2：
            //中间插
            Node* sortPrev = sortHead;//sortPrev是sortcur的前驱结点，方便后续插入
            Node* sortCur = sortPrev->next;//从第二个结点开始往后比较插入
            //从第二个结点往后遍历sorthead链表，找到应该插入的位置
            while(sortCur)
            {
                //找到了 - 插入
                if(cur->val <=sortCur->val)
                {
                    //把cur指向的结点插入到sortPrev结点的后面
                    //相当于 sortPrev cur sortcur 链接
                    sortPrev->next = cur;
                    cur->next = sortCur;
                    break;//插入后，直接跳出循环,进行下一个结点的比较插入
                }
                //否则 - 迭代往后走
                else
                {
                    //sortCur和sortPrev迭代往后走
                    sortPrev = sortCur;
                    sortCur = sortCur ->next;
                }
            }
            // 尾插 - 这里要进行判断，防止是上面插入完成之后,break跳出来的
            if(sortCur == NULL)
            {
                //插入到sortPrev后面
                //相当于sortPrev cur 进行链接
                sortPrev ->next = cur;
                cur->next =NULL;//注意要把此时cur指向的结点的next置空，因为它是尾结点了
            }
        }
        cur = next;//cur迭代往后走
    }
    return sortHead;
}

\