Leetcode : 147. 对链表进行插入排序

���定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。

每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。

重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

思路：设置左右两对指针，分别负责比较和更改；相比于数组多了pre前置指针，用于修改链表的顺序。

#include using namespace std; //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* insertionSortList(ListNode* head) {//         ListNode* slow = head;//         ListNode* fast = head;//         bool flag = false;//         while (slow->next != NULL){//             while (fast->next != NULL){//                 if (fast->val > fast->next->val){//                     ListnodeSwap(fast, fast->next);//                     flag = true;//                 }//                 fast = fast->next;//             }//             if (flag == false) break;//             fast = slow;//             flag = false;//         }//         return head;//     }//     void ListnodeSwap(ListNode* a, ListNode* b){//         int temp = a->val;//         a->val = b->val;//         b->val = temp;//     }// };class Solution {    public:        ListNode* insertionSortList(ListNode* head) {            ListNode* root = new ListNode(0);            ListNode* left_pre = root;            left_pre->next = head;            ListNode* left = head;            ListNode* right = head->next;            ListNode* right_pre = head;            while (right != NULL){                while (left->val val && left != right){                    left_pre = left;                    left = left->next;                }                if (left == right){                    right_pre = right;                    right = right->next;                }else{                    right_pre->next = right->next;                    right->next = left;                    left_pre->next = right;                    if (left == head)                         head = right;                    right = right_pre->next;                }                left = head;                left_pre = root;                }                return head;            }};int main(){    Solution s;    // ListNode* head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3))));    ListNode* head = new ListNode(-1, new ListNode(5, new ListNode(3, new ListNode(4, new ListNode(0)))));    ListNode* res = s.insertionSortList(head);    for (ListNode* i = res; i != NULL; i = i->next){        cout val