[数据结构与算法]使用 插入排序 对链表进行排序

题目：给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
思路：
三个指针，
tmphead用来寻找插入合适位置；
pre负责指向新元素，last 负责指向新元素的前一元素

先用pre和last比较pre指向的元素是否需要执行插入操作
当需要插入时，tmphead指针每次都会从头查找合适位置，
找到合适位置后就重新连接节点关系

//链表插入排序
ListNode*insertionSortList(ListNode *head)
{
	_dummyHead->next=head;
	ListNode*last=head;//最新一次比较的位置
	ListNode*tmphead=_dummyHead;
	ListNode*pre=head->next;//当前需要插入的节点

	while(pre)
	{
		if(last->val<pre->val)
		{
			
			pre=pre->next;
			last=last->next;	
			continue;
		}
		 tmphead=_dummyHead;//这里要让tmphead指向虚头，因为每次给一个节点找插入位置时，都是从头开始找
		//退出if表示pre指向的值需要找合适位置插入，就需要给当前节点找合适位置
		while(tmphead->next->val<pre->val)
		{
			tmphead=tmphead->next;
		}
		//退出循环时表示找到合适位置，就需要修改链表关系
		last->next=pre->next;
		pre->next=tmphead->next;
		tmphead->next=pre;
		pre=last->next;
	}
	return head;
}

测试代码：

/*************************************************************************
	> File Name: 14-对链表进行插入排序.cpp
	> Author: 
	> Mail: 
	> Created Time: Thu 31 Mar 2022 05:19:41 PM CST
	题目：给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
	思路：
	三个指针，
	tmphead用来寻找合适位置；
	pre负责指向新元素，last 负责指向新元素的前一元素
	用pre和last比较pre指向的元素是否需要执行插入操作
	当需要插入时，tmphead指针每次都会从头查找合适位置，
	找到合适位置后就重新连接节点关系
 ************************************************************************/

#include<iostream>
using namespace std;


class Solution 
{
public:   
	struct ListNode
    {
        int val;
        struct ListNode*next;
        ListNode(int val):val(val),next(nullptr){}
    };
	//1. 在链表最前面插入一个节点，插入完成后，新插入的节点为链表的新的头结点
    ListNode*addAtHead(int val) 
    {
        ListNode* newNode = new ListNode(val);
        newNode->next = _dummyHead->next;
        _dummyHead->next = newNode;
        return _dummyHead->next;      
    }

//尾插法
	ListNode*addeare(int val)
	{
 		ListNode* newNode = new ListNode(val);
		ListNode* pre=_dummyHead;
		while(pre->next!=nullptr)
		{
			pre=pre->next;
		}
		//退出循环说明pre的下个位置为空，即链表队尾
		pre->next=newNode;
		return _dummyHead->next;//返回头
	}

// 2.打印链表
    void printLinkedList() 
    {
         ListNode* cur = _dummyHead;
         while (cur->next != nullptr) 
        {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }

//链表插入排序
ListNode*insertionSortList(ListNode *head)
{
	_dummyHead->next=head;
	ListNode*last=head;//最新一次比较的位置
	ListNode*tmphead=_dummyHead;
	ListNode*pre=head->next;//当前需要插入的节点

	while(pre)
	{
		if(last->val<pre->val)
		{
			
			pre=pre->next;
			last=last->next;	
			continue;
		}
		 tmphead=_dummyHead;//这里要让tmphead指向虚头，因为每次给一个节点找插入位置时，都是从头开始找
		//退出if表示pre指向的值需要找合适位置插入，就需要给当前节点找合适位置
		while(tmphead->next->val<pre->val)
		{
			tmphead=tmphead->next;
		}
		//退出循环时表示找到合适位置，就需要修改链表关系
		last->next=pre->next;
		pre->next=tmphead->next;
		tmphead->next=pre;
		pre=last->next;
	}
	return head;
}
	ListNode* _dummyHead= new ListNode(-1); 	
};

int main()
{

// //输入：1 4 3 2 5 2   x=3;
// //输出：1 2 3 4 3 5
	Solution s,s1;
	s.addeare(4);
	s.addeare(2);
	s.addeare(1);


	Solution::ListNode*l1=s.addeare(3);
	s.printLinkedList();//打印移动前数据
	
	Solution:: ListNode*head=s.insertionSortList(l1);//链表向右移动
	s.printLinkedList();//打印移动前数据
	// //打印移动后链表
	// Solution::ListNode*q=head;
	// while(q)
	// {
	// 	cout<<q->val<<" ";
	// 	q=q->next;
	// }
	// cout<<endl;
	return  0;
}