current position:Home>leetcode 148. Sort List(python)
leetcode 148. Sort List(python)
2022-02-01 14:40:57 【Wang Daya】
「 This is my participation 11 The fourth of the yuegengwen challenge 29 God , Check out the activity details :2021 One last more challenge 」
describe
Given the head of a linked list, return the list after sorting it in ascending order.Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?
Example 1:
Input: head = [4,2,1,3]
Output: [1,2,3,4]
Copy code
Example 2:
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Copy code
Example 3:
Input: head = []
Output: []
Copy code
Note:
The number of nodes in the list is in the range [0, 5 * 10^4].
-10^5 <= Node.val <= 10^5
Copy code
analysis
According to the meaning , Is to give the head node of a linked list head , Ask us to sort them in ascending order . The title also requires us to use O(n logn) Time complexity and O(1) Of memory . I tried to insert with the simplest violence , Spatial complexity or O(1), however O(n^2) Time complexity , It's over time .
answer
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:return head
L = ListNode(val=-1000000)
L.next = cur = head
while cur.next:
pre = L
if cur.next.val >= cur.val:
cur = cur.next
continue
while pre.next.val < cur.next.val:
pre = pre.next
tmp = cur.next
cur.next = tmp.next
tmp.next = pre.next
pre.next = tmp
return L.next
Copy code
Running results
Time Limit Exceeded
Copy code
analysis
Because the built-in function is used here sorted Sort values , Re create a new linked list , So the time complexity is O(n logn) But I passed the shame . But the spatial complexity is O(n).
answer
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
node = ListNode(val = 0)
result = node
nlist = []
while head != None:
nlist.append(head.val)
head = head.next
nlist = sorted(nlist)
for n in nlist:
node.next = ListNode(val = n)
node = node.next
return result.next
Copy code
Running results
Runtime: 284 ms, faster than 84.91% of Python online submissions for Sort List.
Memory Usage: 63.3 MB, less than 12.52% of Python online submissions for Sort List.
Copy code
analysis
You can also use merge sort , As long as the time complexity is O(n logn) Other sorting algorithms can .
answer
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:return head
mid = self.getMid(head)
another = mid.next
mid.next = None
return self.merge(self.sortList(head), self.sortList(another))
def getMid(self, head):
fast = slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
return slow
def merge(self, A, B):
dummy = cur = ListNode(0)
while A and B:
if A.val > B.val:
cur.next = B
B = B.next
else:
cur.next = A
A = A.next
cur = cur.next
if A: cur.next = A
if B: cur.next = B
return dummy.next
Copy code
Running results
Runtime: 544 ms, faster than 44.25% of Python online submissions for Sort List.
Memory Usage: 45.6 MB, less than 86.45% of Python online submissions for Sort List.
Copy code
Original link :leetcode.com/problems/so…
Your support is my greatest motivation
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/02/202202011440557874.html
The sidebar is recommended
- Python logging log error and exception exception callback method
- Learn Python quickly and take a shortcut~
- Python from 0 to 1 (day 15) - Python conditional judgment 2
- Python crawler actual combat, requests module, python to capture headlines and take beautiful pictures
- The whole activity collected 8 proxy IP sites to pave the way for the python proxy pool, and the 15th of 120 crawlers
- Why can't list be used as dictionary key value in Python
- Python from 0 to 1 (day 16) - Python conditional judgment 3
- What is the python programming language?
- Python crawler reverse webpack, a real estate management platform login password parameter encryption logic
- Python crawler reverse, a college entrance examination volunteer filling platform encrypts the parameter signsafe and decrypts the returned results
guess what you like
-
Python simulated Login, selenium module, python identification graphic verification code to realize automatic login
-
Python -- datetime (timedelta class)
-
Python's five strange skills will bring you a sense of enrichment in mastering efficient programming skills
-
[Python] comparison of dictionary dict, defaultdict and orderdict
-
Test driven development using Django
-
Face recognition practice: face recognition using Python opencv and deep learning
-
leetcode 1610. Maximum Number of Visible Points(python)
-
Python thread 03 thread synchronization
-
Introduction and internal principles of Python's widely used concurrent processing Library Futures
-
Python - progress bar artifact tqdm usage
Random recommended
- Python learning notes - the fifth bullet * class & object oriented
- Python learning notes - the fourth bullet IO operation
- Python crawler actual combat: crawl all the pictures in the answer
- Quick reference manual of common regular expressions, necessary for Python text processing
- [Python] the characteristics of dictionaries and collections and the hash table behind them
- Python crawler - fund information storage
- Python crawler actual combat, pyteseract module, python realizes the visualization of boos direct employment & hook post data
- Pit filling summary: Python memory leak troubleshooting tips
- Python code reading (Chapter 61): delaying function calls
- Through the for loop, compare the differences between Python and Ruby Programming ideas
- leetcode 1606. Find Servers That Handled Most Number of Requests(python)
- leetcode 1611. Minimum One Bit Operations to Make Integers Zero(python)
- 06python learning notes - reading external text data
- [Python] functions, higher-order functions, anonymous functions and function attributes
- Python Networkx practice social network visualization
- Data analysis starts from scratch, and pandas reads and writes CSV data
- Python review (format string)
- [pandas learning notes 01] powerful tool set for analyzing structured data
- leetcode 147. Insertion Sort List(python)
- apache2. 4 + windows deployment Django (multi site)
- Python data analysis - linear regression selection fund
- How to make a python SDK and upload and download private servers
- Python from 0 to 1 (day 20) - basic concepts of Python dictionary
- Django -- closure decorator regular expression
- Implementation of home page and back end of Vue + Django tourism network project
- Easy to use scaffold in Python
- [Python actual combat sharing] I wrote a GIF generation tool, which is really TM simple (Douluo continent, did you see it?)
- [Python] function decorators and common decorators
- Explain the python streamlit framework in detail, which is used to build a beautiful data visualization web app, and practice making a garbage classification app
- Construction of the first Django project
- Python crawler actual combat, pyecharts module, python realizes the visualization of river review data
- Python series -- web crawler
- Plotly + pandas + sklearn: shoot the first shot of kaggle
- How to learn Python systematically?
- Analysis on several implementations of Python crawler data De duplication
- leetcode 1616. Split Two Strings to Make Palindrome (python)
- Python Matplotlib drawing violin diagram
- Python crawls a large number of beautiful pictures with 10 lines of code
- [tool] integrated use of firebase push function in Python project
- How to use Python to statistically analyze access logs?