LeetCode题解之Insertion Sort List

时间:2022-03-01 11:06:05

1、题目描述

LeetCode题解之Insertion Sort List

 

2、题目分析

利用插入排序的算法即可。注意操作指针。

 

3、代码

 1 ListNode* insertionSortList(ListNode* head) {
 2         if (head == NULL || head->next == NULL)
 3             return head;
 4         
 5         ListNode *dummy = new ListNode(0);
 6         dummy->next = head;
 7         ListNode *pre = dummy;
 8         ListNode *p = head;
 9         ListNode *pn = head->next;
10         
11         while (pn != NULL) {
12             pre = dummy;
13             p = dummy->next;
14             while (p->val < pn->val) {
15                 p = p->next;
16                 pre = pre->next;
17             }
18             
19             ListNode *tmp = pn->next;
20             pre->next = pn;
21             pn->next = p;
22             
23             while (p->next != pn)
24                 p = p->next;
25             p->next = tmp;
26             pn = tmp;
27         }
28         
29         return dummy->next;
30         
31     }