Leetcode
medium
list
sort
python
c++
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.
Learn More →
Learn More →
#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]
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
#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;
}
###### tags: Leetcode easy python c++ string Top 100 Liked Questions
Aug 21, 2023[題目連結:] https://leetcode.com/problems/koko-eating-bananas/ 題目: 解題想法: 此題為有n串香蕉,第i串有piles[i]根香蕉守衛h小時回來 設一小時能吃k根香蕉吃完第i串後無法再同一小時內吃另外第j串 若第i串有x根香蕉,且x<k,則依舊需要等該小時過完,才能繼續下一串,意思為: 若有餘數需無條件進位1小時 求k使得能以最慢速度吃完所有香蕉
Mar 30, 2023[題目連結:] https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/ 題目: 解題想法: 此題為給一target目標節點,返回所有跟target相距k步的節點各點值皆不重複 可往上拜訪父點,也可往下拜訪子點 DFS+BFS拜訪 所需工具:dic= collections.defaultdict(list){key:某點的值 ; value:與他相連的所有鄰居的值}
Mar 29, 2023[題目連結:] https://leetcode.com/problems/range-sum-query-immutable/description/ 題目: 解題想法: 此題為設計實做一個NumArray類別,使用sumRange(i, j) 時要能夠回傳[i, j]範圍內的和 prefix sum前綴和想法self.nums紀錄原本的數組 self.sumArray紀錄從頭到nums[i]的和 最終 self.sumArray[right]-self.sumArray[left]+self.nums[left]即為解 ex: nums =[-2, 0, 3, -5, 2, -1]
Mar 29, 2023or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up