5. insertion-sort-list 链表插入排序

阳光穿透心脏的1/2处 2022-05-23 11:24 134阅读 0赞

## 题目描述 ##

Sort a linked list using insertion sort.

对一个链表进行插入排序

## 题目解析 ##

上一道题对链表进行归并排序和冒泡排序 详细可见https://blog.csdn.net/qq\_28351465/article/details/78500992

对链表进行插入排序，依次对链表进行遍历，遍历到哪个节点，哪个节点之前的全部节点是已排序好的，然后再依次访问已排序好的节点，如果节点值大于该次遍历的值，那么进行插入操作。插入操作需要知道 遍历点 和其前后点、插入点前后点，相对来说，代码写的较麻烦。对链表进行操作时，要始终不要害怕把链表拆掉，即可构建一个新的链表，每次将遍历点放入新链表的合适位置，就能大大简化代码，代码详细如下：

/**
     * 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 (NULL == head || NULL == head->next) return head;
            
            ListNode *loop = head;
            ListNode tmp(0);
            ListNode *p = NULL;
            ListNode *q = NULL;
            ListNode *i = NULL;
            
            while (NULL != head)
            {
                p = &tmp;
                q = p->next;
                
                i = head;
                head = head->next;
                
                while (q && q->val < i->val)
                {
                    p = p->next;
                    q = q->next;
                }
                
                p->next = i;
                i->next = q;
            }
            
            return tmp.next;
        }
    };