题解 | #链表的插入排序#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

class Solution {
  public:
    /**
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* insertionSortList(ListNode* head) {
        // write code here
        ListNode* sorted = nullptr; // 新的排序链表

        while (head) {
            ListNode* current = head; // 当前节点
            head = head->next; // 移动原链表的指针

            sorted = sortedInsert(sorted, current); // 插入到排序链表
        }

        return sorted;
    }
  private:
    ListNode* sortedInsert(ListNode* head, ListNode* newNode) {
        if (!head || newNode->val < head->val) {
            newNode->next = head;
            return newNode; // 新节点成为头
        }

        ListNode* current = head;
        while (current->next && current->next->val < newNode->val) {
            current = current->next; // 找到插入位置
        }

        newNode->next = current->next; // 插入新节点
        current->next = newNode;

        return head;
    }
};