算法题：非递归插入排序

题目描述

Sort a linked list using insertion sort.

分析

插入排序

非递归解法
递归解法

非递归

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (!head)
            return head;
        //临时节点
        ListNode temp(0);
        
        ListNode* p1=NULL;
        ListNode *p2=NULL;
        ListNode *t=NULL;
        while(head)
        {
            //冻结节点
            p1 = &temp;
            
            p2 = p1->next;
            t = head;
            head = head -> next;
            //找到插入点
            while(p2&&p2->val < t->val)
            {
                p1 = p1->next;
                p2 = p2->next;
            }
            //插入节点
            t->next = p2;
            //接上节点
            p1->next = t;
        }
        return temp.next;
    }
};

递归法

class Solution {
public:
    ListNode *insertionSortList(ListNode *head) {
        if (!head || !head->next)
            return head;
        //临时节点
        ListNode temp(0);
        ListNode* p=NULL;
        //递归
        temp.next = insertionSortList(head->next);
        p = &temp;
        //
        while(p && p->next && head->val > p->next->val)
        {
            p = p->next;
        }
        head->next = p->next;//插入
        p->next = head;//拼接
        
        return temp.next;
    }
};