Insertion Sort List leetcode

?

连用插入排序法将链表排序

?

为了方便，只定义一个头节点。

思路：

?

定义头结点 result 令 result->next =head , 然后将链表中的值一一取出来，然后插入到合适的位置 插入之前要先断开链表 新链表刚开始只有一个元素 head

?

令p=head->next p往后遍历， 将p的值插入到合适的新链表中

?

代码如下：

?

?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        
        if(head==NULL||head->next==NULL)
            return head;
        ListNode *result=new ListNode(0);
        result->next=head;
        
        ListNode *pur,*p,*temp;//定义两个指针  pur用来指向当前链表的第一个（指插入排序后前面有序的第一个）temp用来记录pur的前一个节点 p用来遍历旧链表
        
        
        p=head->next;
        temp=result;
        pur=head; //pur用来遍历新链表
        
        pur->next=NULL;//断开链表
        
        while(p)  //遍历旧链表
        {
            ListNode *q=p->next;   //保存p的下一个节点
            p->next=NULL;
            
            while(pur&&pur->val
   
    val)//将旧链表中的值插入到新链表中去 { temp=pur; //temp记录pur的前一个节点，做插入用 pur=pur->next; } p->next=pur; //插入节点p temp->next=p; temp=result; //由于上面操作改变了原值，所以temp和pur要还原 pur=temp->next; p=q; //令p继续遍历 } return result->next; } };
   

?