Try   HackMD
tags: Leetcode medium list sort python c++

147. Insertion Sort List

[題目連結:] https://leetcode.com/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:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.

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.

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.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

解題想法:

  • 將node由小到大排序:
    • 每個node逐一檢查加入

Python_Sol1:

#Insertion Sort List class ListNode(object): def __init__(self, val=0, next=None): self.val = val self.next = next def insert(self,node): if self.next==None: self.next=ListNode(node) else: self.next.insert(node) def printList(self): head=self stack=[] while head: stack.append(head.val) head=head.next print(stack) class Solution(object): def insertionSortList(self, head): """ :type head: ListNode :rtype: ListNode """ dummy=ListNode(0) while head: cur=head #當前node pre=dummy head=head.next #記錄下個起始點 #決定cur應該插入在pre為首的哪個位置 while pre.next and cur.val>pre.next.val: pre=pre.next cur.next=pre.next pre.next=cur return dummy.next if __name__=='__main__': root = ListNode(4) root.insert(2) root.insert(1) root.insert(3) print("Old :",end='') root.printList() #Old :[4, 2, 1, 3] result=Solution() ans = result.insertionSortList(root) print("After:",end='') ans.printList() #After:[1, 2, 3, 4]

Python_Sol2:

  • 逐一檢查每個node是否在正確位置
    • 小->大
    • 當前node.val<=node.next.val
  • 若不合格: 針對node.next決定其插入位置
    • 從頭找合適的位置插入
class Solution(object): def insertionSortList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head or not head.next: return head dummy=ListNode(float('-inf')) dummy.next=head while head.next: #若安全是小->大 if head.val<=head.next.val: head=head.next else: pre=dummy cur=head.next #從頭找合適的位置 while pre.next and cur.val>pre.next.val: pre=pre.next #連至合適的位置 head.next=head.next.next cur.next=pre.next pre.next=cur return dummy.next

C++:

#include<iostream> #include<vector> using namespace std; 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) {} }; void InsertNode(ListNode *head, int data){ ListNode *tail=head; if (tail->next==nullptr){ ListNode *new_node= new ListNode(data); tail->next=new_node; } else InsertNode(tail->next,data); } void PrintList(ListNode *head){ vector<int> res; ListNode *tail=head; while (tail!=nullptr){ res.push_back(tail->val); tail=tail->next; } for (int i=0; i<res.size(); i++){ cout<<res[i]<<" "; } cout<<endl; } class Solution { public: ListNode* insertionSortList(ListNode* head) { ListNode *dummy =new ListNode(0), *pre=dummy; while (head){ ListNode *cur=head; pre=dummy; head=head->next; while (pre->next && cur->val>pre->next->val){ pre=pre->next; } cur->next=pre->next; pre->next=cur; } return dummy->next; } }; int main(){ ListNode *head=new ListNode(4); InsertNode(head,2); InsertNode(head,1); InsertNode(head,3); cout<<"Original List: "; PrintList(head); //Original List: 4 2 1 3 Solution res; ListNode *ans=res.insertionSortList(head); cout<<"After Sorted : "; PrintList(ans); //After Sorted : 1 2 3 4 return 0; }