LeetCode147:Insertion Sort List

题目：

Sort a linked list using insertion sort.

解题思路：

按题目要求，直接进行插入排序

实现代码：

#include <iostream>

using namespace std;
/*
Sort a linked list using insertion sort.
 */
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x):val(x), next(NULL){}    
};

void addNode(ListNode* &head, int val)
{
    ListNode *newNode = new ListNode(val);
    if(head == NULL)
    {
        head = newNode;
    }
    else
    {
        newNode->next = head;
        head = newNode;
    }
}

void PrintList(ListNode *root)
{
    ListNode *head = root;
    while(head != NULL)
    {
        cout<<head->val<<"	";
        head = head->next;
    }
    cout<<endl;
}

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *p = head->next;//保存除第一个节点之后的所有节点，待之后逐个进行插入排序 
        head->next = NULL;       
        while(p)
        {
            ListNode *t = p->next;//保存p节点的下一个节点 
            if(p->val < head->val)//如果当前要插入的节点小于头节点 
            {
                
                p->next = head;
                head = p;//将头结点指向新插入的节点           
            }
            else//否则从头结点的下一个节点开始逐个与当前要插入节点比较，直到遇到大于当前节点的节点 
            {
                ListNode *q = head;
                while(q->next && q->next->val <= p->val)
                    q = q->next;
    
                p->next = q->next;
                q->next = p;    
            }
            p = t;
        }
        return head;                
    }
};

int main(void)
{
    ListNode *head = new ListNode(5);
    addNode(head, 3);
    addNode(head, 10);
    addNode(head, 15);
    PrintList(head);
    
    Solution solution;
    head = solution.insertionSortList(head);
    PrintList(head);
    
    return 0;
}