Umgekehrte einzelne verkettete Liste

Question

Ich implementierte die "reverse single linked list, do-in-place" Aufgabe. Ich kam mit dieser Lösung:

/** 
* Definition for singly-linked list. 
* public class ListNode { 
*  int val; 
*  ListNode next; 
*  ListNode(int x) { val = x; } 
* } 
*/ 
public class Solution { 
    public ListNode reverseList(ListNode head) { 
     if (head == null) { 
      return null; 
     } 

     if(head.next==null) return head; 

     ListNode n = head; 
     ListNode r = null; 
     ListNode temp = null; 

     while (n != null) { 
      temp = n; 
      n = n.next; 
      temp.next = r; 
      r = temp; 
     } 

     return r; 
    } 
} 

und es funktioniert:

1 2 3 4 5 
5 4 3 2 1 

aber wenn ich wollte sicher sein, es ist der richtige Ansatz, alle Lösungen Ich habe Online wie die Reverse single linked list so aussehen gesehen I fing an, mich selbst zu befragen ... Was ist los mit meiner Lösung? Die Zeitkomplexität sieht wie O (n) space com aus. O (1) ... liege ich falsch? Danke im Voraus!

Answer 1

Nicht sicher, was Sie fragen. Ihre Implementierung sieht fast genauso aus wie in der Verknüpfung. Beide Implementierungen sind O(n) für die Zeitkomplexität und O(1) für die Raumkomplexität. Natürlich ist die Liste selbst O(n) für Raumkomplexität.