[LeetCode] Insertion Sort List
2023-09-11 14:17:25 时间
分析:把链表分成两部分:排好序的和为排序的,排好序的以NULL结尾,cur插在preInsertion和insertion之间,next保存cur->next.
另外,注意dummy的使用简化了插入头结点的情况。
时间复杂度O(n^2),空间O(1)
/** * 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 NULL; ListNode dummy(INT_MIN); dummy.next = head; ListNode* preInsertion = NULL; ListNode* insertion = NULL; ListNode* cur = head->next; head->next = NULL;//break the sorted and unsorted ListNode* next = NULL; while(cur) { preInsertion = & dummy; insertion = dummy.next; //find the right position while(insertion != NULL && cur->val >= insertion->val) { preInsertion = preInsertion->next; insertion = insertion->next; } #if 0 if(insertion == NULL)//cur is max, don't need to move it { next = cur->next;//just store cur first; preInsertion->next = cur; cur->next = NULL; cur = next; } else { next = cur->next;//just store cur first; preInsertion->next = cur; cur->next = insertion; cur = next; } #endif next = cur->next;//just store cur first; preInsertion->next = cur; cur->next = insertion; cur = next; } return dummy.next; } };
相关文章
- leetcode 之Rotate List(18)
- Java实现 LeetCode 421 数组中两个数的最大异或值
- Java实现 LeetCode 380 常数时间插入、删除和获取随机元素
- Java实现 LeetCode 234 回文链表
- Java实现 LeetCode 208 实现 Trie (前缀树)
- Java实现 LeetCode 114 二叉树展开为链表
- [Algorithm] 234. Palindrome Linked List / Reverse linked list
- (LeetCode 203)Remove Linked List Elements
- [LeetCode] Flatten Nested List Iterator
- [LeetCode] Reverse Linked List II
- [LeetCode] Reverse Linked List(递归与非递归反转链表)
- [LeetCode] Linked List Cycle II
- [LeetCode] Reorder List
- LeetCode-67. 二进制求和【位运算,字符串,数学,模拟】
- LeetCode-1752. 检查数组是否经排序和轮转得到【数组】
- [LeetCode] 83. Remove Duplicates from Sorted List ☆(从有序链表中删除重复项)
- [LeetCode]Linked List Cycle
- LeetCode之Sort List
- leetcode 206. Reverse Linked List
- List<?> list= new ArrayList<?>接口引用指向实现类的对象.