算法题：非递归插入排序

题目描述

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; } };

总结

插入排序： 添加了个伪链表头，简化设计