[PYTHON] Lassen Sie Code Day78 von vorne beginnen "206. Reverse Linked List"

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Anscheinend ergreifen viele Ingenieure Maßnahmen auf der Website namens LetCode.

Es ist eine Site, die die Algorithmusleistung trainiert, die dem Codierungstest standhält, der in der frühen Geschichte durchgeführt wird, und es ist ein unvermeidlicher Weg für diejenigen, die eine Karriere bei einem ausländischen Technologieunternehmen aufbauen möchten.

Ich habe es großartig geschrieben, aber ich habe im Moment keine Pläne für ein solches Interview.

Als IT-Ingenieur wäre es jedoch besser, die gleiche Algorithmusleistung wie eine Person zu haben. Daher möchte ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Ich löse es mit Python3.

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Day 77 ab Null "1502. Kann arithmetische Fortschritte aus der Sequenz machen"

Im Moment priorisiere ich das Medium der 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.

Twitter Ich mache es.

** Technischer Blog Gestartet! !! ** **. Ich denke, die Technologie wird über LetCode, Django, Nuxt usw. schreiben. ** Dies ist schneller zu aktualisieren **, vielen Dank für Ihre Mitarbeit!

Problem

206. Reverse Linked List Der Schwierigkeitsgrad ist einfach.

Das Problem ist, dass Sie nur eine bestimmte unidirektionale verkettete Liste umdrehen.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Lösung

Vorerst iterative Dinge.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre,cur = None,head
        while cur != None:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre
# Runtime: 44 ms, faster than 26.15% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.3 MB, less than 67.33% of Python3 online submissions for Reverse Linked List.

Bereiten Sie drei Variablen vor, "pre", "cur" und "nex", und behalten Sie die vorherigen, aktuellen und nachfolgenden Elemente bei und ersetzen Sie sie. Stellen Sie sich das als ein Bild vor, in dem Variablen vorbereitet und temporäre Fluchtbereiche für jede erstellt werden.

Wenn dies jedoch unabhängig von der Skalierung der Fall ist und die Anzahl der Variablen zunimmt, nimmt der Verarbeitungsaufwand zu und das Schreiben ist mühsam. Immerhin möchte ich Spaß haben.

Hier ist die Antwort mit Stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        
        stack = []
        
        while head.next:
            stack.append(head)
            head = head.next
            
        while stack:
            cur = stack.pop()
            cur.next.next = cur
            cur.next = None
            
        return head
# Runtime: 40 ms, faster than 46.28% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.1 MB, less than 96.42% of Python3 online submissions for Reverse Linked List.

Ich mag dieses, weil ich es sauber schreiben kann, ohne es zu vermasseln. Und ein bisschen hat sich die Geschwindigkeit verbessert.

Ich habe zwei Beispiele für Antworten geschrieben, aber wie wäre es damit?

Ist das nicht schlauer und besser? Wenn Sie eine Meinung haben, wäre ich Ihnen dankbar, wenn Sie einen Kommentar abgeben könnten.