单链表插入排序算法

约定不等于承诺〃 2022-08-26 12:15 179阅读 0赞

如果数据存储在一段连续的内存上，比如数组中，插入排序算法的实现相信大家都已经非常熟悉，如果要对一个单链表进行插入排序，将会牵扯到大量指针操作。

同时，如果在实现的过程中适当使用一些小技巧，将会减少指针操作的次数，同时也减少出错的危险。

插入排序的原理相信大家都已经了然于胸，这里就不在赘述，下面直接给出实现代码：

如有错误之处，还望不吝指教，共同学习进步：

#include <iostream>
    using namespace std;
    
    struct ListNode {
         int val;
         ListNode *next;
         ListNode(int x) : val(x), next(NULL) {}
     };
    
    class Solution {
    public:
        ListNode *insertionSortList(ListNode *head) {
    
    		if (!head) return NULL ;
    
    		ListNode* preHead = new ListNode(INT_MIN) ; //作为哨兵节点
    		preHead->next = head ;
    		head = preHead ;
    
    		ListNode* p1 = head->next ;//指向要进行插入排序的节点的前一个节点
    		ListNode* p2 = head ; //指向插入位置的前一个节点
    
    
    		while(p1 ->next != NULL)
    		{
    			p2 = head ;
    			while (p2->next != p1->next && p1->next->val > p2->next->val)
    				p2 = p2->next ;
    
    			if (p2->next != p1->next)
    			{
    				ListNode* tmpP1 = p1->next ;
    				p1->next = p1->next->next ;
    
    				tmpP1->next = p2->next ;
    				p2->next = tmpP1 ;
    			}
    			else
    				p1 = p1->next ; //不交换的时候才移动p1指针，否则不移动
    		}
    
    		preHead = head ;
    		head = head->next ;
    		delete preHead ;
    
    		return head ;
        }
    };
    
    
    int main(int argc, char **argv)
    {
    	ListNode *head = NULL ;
    	ListNode *tail = NULL ;
    	int n ;
    	//输入数据
    	while (cin >> n)
    	{
    		ListNode *newNode = new ListNode(n) ;
    		if (head == NULL)
    		{
    			head = newNode ;
    			tail = newNode ;
    		}
    		else
    		{
    			tail->next = newNode ;
    			tail = newNode ;
    		}
    	}
    
    	//插入排序
    	Solution s ;
    	head = s.insertionSortList(head) ;
    
    	//输出排序结果
    	ListNode* p = head ;
    	while(p != NULL)
    	{
    		cout << p->val << " " ;
    		p = p->next ;
    	}
    	cout << endl ;
    	
    	//删除空间
    	p = head ;
    	while (p)
    	{
    		ListNode* tmp = p ;
    		p = p->next ;
    		delete tmp ;
    	}
    
    	return 0 ;
    }