题解 | #对链表进行插入排序#

对链表进行插入排序

https://www.nowcoder.com/practice/cc6c61215dfb446f8eccea3663e3d8db

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        ListNode* p = head;
        while(p->next)
        {
            // 去找到这个比前一个值小的结点位置
            while(p->next && p->next->val > p->val)
                p = p->next;
            // 如果为空 则 返回
            if(p->next == nullptr) return head;
            // 如果不为空 则 找到异常值 位置 选择合适的位置进行插入
            ListNode* tmp = new ListNode(p->next->val);
            // 加入比头结点小,直接插到头结点位置
            if(tmp->val < head->val)
            {
                tmp->next = head;
                head = tmp;
            }
            // 否则找到合适的位置插入
            else
            {
                // 从头结点位置开始找到合适的位置
                ListNode* t = head;
                // 插入的位置的值 一定是比前一个值大 
                while(t->next && t->next->val < tmp->val)
                    t = t->next;
                // 插入操作
                tmp->next = t->next;
                t->next = tmp;
            }
            // 跳过被插入的位置,因为已经有序了
            p->next = p->next->next;
        }
        return head;
    }
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 14:00
不想多说了,什么逆天HR,还要教我礼貌😂
机械打工仔:这不纯傻卵吗,他还操心上别人老板了
投递BOSS直聘等公司7个岗位
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:31
点赞 评论 收藏
分享
白火同学:大二有这水平很牛了,可以适当对关键信息加粗一点,比如关键技术、性能指标之类的。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务