单链表插入排序算法-蒲公英云

单链表插入排序算法

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

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

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

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

#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 ;
}