这是一道 指针题目。
指针是最烦的,但是弄清楚指针的原理,这样的题目也可以轻松过。
思路就是遍历链表,没遍历到一个新的节点,都把它和从头开始比,遇到第一个比它大的就插进去。
写的过程中一定要小心,很容易就写错。
c++ 题解
/**
* 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)
return head;
ListNode* term = head->next;
ListNode* term2 = head;
ListNode* pre = head;
ListNode* pre2 ;
int tag;
while(term!=NULL)
{
tag=0;
while(term2!=term)
{
if( term->val < term2->val)
{
pre->next = term->next;
term->next = term2;
if(pre2!=NULL)
pre2->next = term;
else
head = term;
term = pre->next;
tag=1;
break;
}
pre2 = term2;
term2 = term2->next;
}
pre2 = NULL;
term2 = head;
if(tag==1)
continue;
pre = term;
term = term->next;
}
return head;
}
};