Leetcode-hot100

Leetcode hot 100: 排序链表

By crabboss 2024 年 5 月 28 日 #Leetcode, #插入排序, #链表

排序链表

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

选择插入排序算法：

插入排序算法的原理是让锚点前面的数值都有序，每次都从锚点之后找到一个值往前插入。

分为两步：

1 遍历链表
2 从链表中找到合适的插入位置

一些小细节，先去原始链表中找到一个节点，然后从dummy节点开始找到适合插入的位置原始链表少一个几点，dummy链表多一个节点）：

1 遍历链表是从head开始
2 在从链表中找到合适的插入位置之前需要保存好cur的下一个位置，用于更新遍历链表
3 从链表中找到合适的插入位置是从dummy节点开始。
4 链表的插入需要先顾尾后顾头
5 链表的循环从head开始，到最后一个节点结束.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = head;
        while(cur){
            ListNode* in_cur = dummy;
            ListNode* next_node = cur->next;
            while(in_cur->next && in_cur->next->val <= cur->val){
                in_cur = in_cur->next;
            }
            cur->next = in_cur->next;
            in_cur->next = cur;
            cur = next_node;
        }
        return dummy->next;
    }
};