王道2-2-6

题目大意

给定一个头结点链表，按照从小到大排序

思路

根据插入排序的思路和逆置链表的思路，首先先把头结点和他的next摘出p，让p为读取元链表的节点，pre为摘出来新链表的头结点，然后pre遍历，小于p.val的就继续，不然就是正常的插入。

代码实现

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; //本题思路插入排序，头插法类似，吧l取出，做个新链表 class Solution { public: void deleteNode(ListNode* node) { ListNode *p=node.next,*q=p.next; //pre是断链后端头插法节点 ListNode *pre; //进行断链 p.next=NULL; //进行替换 p=r; while(p!=NULL){ r=p.next; pre=node; while(pre.next!=null&&pre.next.val<p.val){ pre=pre.next; } p.next=pre.next; pre.next=p; p=r; //进行下一轮 } } }