LeetCode Algorithm 147. 对链表进行插入排序

LeetCode Algorithm 147. 对链表进行插入排序

题目链接：​​147. 对链表进行插入排序​​

Ideas

算法：插入排序 数据结构：链表 思路：定义一个lastSorted指针指向最后一个排好序的节点，再定义一个cur指针指向当前正在进行判断的节点，如果最后一个排好序的节点值小于当前正在判断的节点值，那么lastSorted指针和cur指针后移即可，否则说明需要将当前节点往前插入，首先定义一个pre节点指向头节点，如果pre的下一个节点值大于cur的节点值，那么就要把cur插入到pre节点的后方即可。

Code

C++

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。