2023-02-20 leetcode-insertionSortList

摘要:

记录leetcode-insertionSortList的反思

要求:

https://leetcode.cn/problems/insertion-sort-list/

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

The steps of the insertion sort algorithm:

1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

数据结构相关:

1. 链表
2. 单向链表
3. 指针

思路:

1. 其实还是基于链表的特性，给链表排序, 在不要求时间复杂度的情况下, 直接插入排序
2. 算法倒是很直白暴力, 没有太多弯弯绕绕的,所以可以拿这个当作切入
3. 重点就在于对链表这个数据结构的操作了，此处尤其要注意边界
   1. 链表为空的场景
   2. 链表的首元素处理
   3. 链表的尾元素处理
   4. 向链表插入元素的指针处理
4. 单向链表作为各种数据结构中最简单的, 基本操作如果不能熟练掌握是不能有借口的
5. 并且单链表的操作，基本只涉及指针处理, 可以体现对指针的理解

更深一层的思考:

1. 最基本的思考是对于原有链表的遍历, 和对新链表的遍历插入
2. 如果用最朴素的做法, 那么时间复杂度将是O(n^2)
3. 问题的关键在于对于新的链表, 不用从头遍历, 就能找到要插入的位置

关于新链表插入位置的思考:

1. 可以换个思路，每次遍历旧链表，都找出比上次大的元素
2. 这样在插入新链表的时候, 就只用插入新链表的末尾

题解:

题解一:

struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:ListNode* insertionSortList(ListNode* head) {if(!head || !head->next) return head;ListNode *sorted_head = new ListNode(-1);sorted_head->next = head;ListNode *curr = head;while(curr && curr->next){if(curr->val <= curr->next->val) curr=curr->next;else{ListNode *tmp = curr->next;curr->next = tmp->next;ListNode *insert_node = sorted_head;while(insert_node->next->val <= tmp->val ) insert_node = insert_node->next;// insert the node into sorted list tmp->next = insert_node->next;insert_node->next = tmp;}}return sorted_head->next;}
};                    

题解二:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};ListNode *insertionSortList(ListNode *head) {// zero or one element in listif (head == NULL || head->next ==NULL){return head;}ListNode *pSorted = NULL;while ( head != NULL  ){/* remember the head */ListNode *pHead = head;/* trailing pointer for efficient splice */ListNode **ppTrail = &pSorted;/* pop head off list */head = head->next;/* splice head into sorted list at proper place */while( *ppTrail!=NULL && pHead->val > (*ppTrail)->val )  {ppTrail = &(*ppTrail)->next;}pHead->next = *ppTrail;*ppTrail = pHead;}return pSorted;
}void printList(ListNode* h)
{while(h!=NULL){printf("%d ", h->val);h = h->next;}printf("\n");
}ListNode* createList(int a[], int n)
{ListNode *head=NULL, *p=NULL;for(int i=0; i<n; i++){if (head == NULL){head = p = new ListNode(a[i]);}else{p->next = new ListNode(a[i]);p = p->next;}}return head;
}int main(int argc, char** argv)
{int n = 10;if (argc>1){n = atoi(argv[1]);}srand(time(NULL));int *a = new int[n];for(int i=0; i<n; i++){a[i] = rand()%n + 1;}ListNode *p = createList(a, n);printList(p);printList(insertionSortList(p));delete[] a;
}