Insertion Sort List

原题链接

Sort a linked list using insertion sort

题意:实现链表插入排序

思路与数组的插入排序是类似的,保持对当前节点排序的时候前面的链表已经是有序的,然后寻找到应该插入的位置,插入当前节点完成一趟排序操作。直到遍历完所有节点,排序也完成了。

图示如下:

代码如下:

虽然我们思路很清晰,但是链表的操作总是很玄妙,这个写法看起来很简洁,但是需要注意,构造假头节点dummy的时候,并没有把dummy与原链表链接,而是在第一次循环中pre->next = cur链接起来的,还有就是先把当前节点的下一个节点保存,以免在移动节点时混淆

还有一个做法,感觉比较混乱

发表评论

电子邮件地址不会被公开。