单链表冒泡排序

#include<iostream>
using namespace std;

struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

ListNode* create();
ListNode *BubbleSort(ListNode *head);

int main()
{
    ListNode* head = create();
    head = BubbleSort(head);

    ListNode* ptr = head;                          //观察排序后的结果
    while(ptr != NULL)
    {
        cout<<ptr->val<<endl;
        ptr = ptr->next;
    }
}

ListNode* create()                                  //构建单链表
{
    ListNode* pre = new ListNode(0);                //申请一个头结点
    ListNode* cur = pre;
    for(int i=1; i<=5; ++i)
    {
        ListNode* newNode = new ListNode(i);
        cur->next = newNode;
        cur = newNode;
    }
    cur->next = NULL;
    ListNode *head = pre->next;
    return head;
}


ListNode* BubbleSort(ListNode* head){                               //单链表 冒泡排序
    if(head == NULL || head->next == NULL) return head;
    ListNode* pHead = new ListNode(0);                              //申请一个头结点
    pHead->next = head;

    ListNode* ptr1 = head;
    int count_ = 0;
    while(ptr1!=NULL)                                               //统计链表中结点个数
    {
        count_++;
        ptr1 = ptr1->next;
    }

    while(count_ >= 1)
    {
        ListNode* beforeP = pHead;
        while(beforeP->next->next != NULL)
        {
            ListNode* p = beforeP->next;
            ListNode* afterP = p->next;
            if(p->val < afterP->val)                                  //交换相邻结点
            { 
                beforeP->next = p->next;
                p->next = afterP->next;
                afterP->next = p;
            }
            beforeP = beforeP->next;
        }
        count_--;
    }
    return pHead->next;
}