147. 对链表进行插入排序

发表于 2023-07-02 更新于 2023-07-04 分类于力扣阅读次数： Waline：本文字数： 224 阅读时长 ≈ 1 分钟

考点

链表的排序

题解

class Solution {
	public:
		ListNode* insertionSortList(ListNode* head) {
			ListNode *dummyHead = new ListNode(-1, head);
			while (head->next != nullptr) {
				if (head->val > head->next->val) {
					ListNode *cur = dummyHead, *node = head->next;
					while (cur->next != nullptr && cur->next->val < node->val ) cur = cur->next;
					head->next = node->next;
					node->next = cur->next;
					cur->next = node;
				} else {
					head = head->next;
				}
			}
			return dummyHead->next;
		}
};