EEPW论坛

Sort a linked list using insertion sort.

题意：利用插入排序的思想实现链表排序；

思路：

从第二个指针开始，如果前一个指针p小于后一个指针q，则q直接连接到p后面；

否则，从头查找比q大的指针，然后进行插入；

1. class Solution  

2. {  

3. public:  

4.   

5.     ListNode* insertionSortList(ListNode* head)  

6.     {  

7.         if (head==NULL || head->next==NULL)  

8.         {  

9.             return head;  

10.         }  

11.   

12.         ListNode* pre = new ListNode(-1);  

13.         pre->next = head;  

14.   

15.         ListNode* nHead = pre;  

16.         ListNode* p = head;  

17.         ListNode*q = head->next;  

18.   

19.         while (q)  

20.         {  

21.             if (q->val>=p->val)  

22.             {  

23.                 p->next = q;  

24.                 p = q;  

25.                 q = p->next;  

26.             }  

27.             else  

28.             {  

29.                 pre = nHead;  

30.                 //从头遍历  

31.                 while (pre->next->val<q->val)  

32.                 {  

33.                     pre = pre->next;  

34.                 }  

35.   

36.                 p->next = q->next;  

37.                 q->next = pre->next;  

38.                 pre->next = q;  

39.                 q = p->next;  

40.             }  

41.         }  

42.   

43.         return nHead->next;  

44.     }  

45. };