LeetCode: Soluție și explicație pentru inversarea unei liste înlănțuite
Scris de Denis Nuțiu
- 2 minute de citit
- 1 exemplu de cod
Disponibil și în English
Pe această pagină
Salut,
În acest articol explic soluția mea pentru următoarea problemă LeetCode: Reverse Linked List.
Dacă ești interesat să rezolvi această problemă, încearcă să petreci cel puțin o oră sau mai mult pe ea înainte de a-mi vedea soluția.
Ca să te ajut să rezolvi problema, am creat următorul tabel:
| Current | Prev |
|---|---|
| 1 | NULL |
| 2 | 1 |
| 3 | 2 |
| NULL | 3 |
Gândește-te cum poți folosi acest tabel ca să scrii un algoritm iterativ sau recursiv care inversează lista înlănțuită.
Soluția
Mai jos găsești soluțiile mele iterativă și recursivă, cu explicații. Soluțiile sunt scrise în C#.
Soluția recursivă
Dacă te uiți la tabelul pe care l-am făcut, poți observa că, pentru a inversa lista, tot ce trebuie să faci este să faci nodul curent să indice spre nodul anterior în fiecare apel recursiv, apoi să treci la nodul următor.
Condiția de oprire apare când nodul curent este null. Atunci trebuie să returnezi nodul anterior, care indică spre nodul anterior, care indică spre cel dinaintea lui și așa mai departe. Ai obținut o listă înlănțuită inversată.
Complexitatea este O(n) pentru timp, pentru că trebuie să parcurgem întreaga listă, și O(n) pentru spațiu, pentru că la fiecare apel programul alocă un nou cadru de stivă.
Soluția iterativă
Soluția iterativă este asemănătoare cu cea recursivă, doar că nu alocă spațiu suplimentar; pur și simplu parcurge lista, modificând-o direct.
Actualizează nodul curent la cel anterior și, la final, returnează ultimul nod.
Complexitatea este O(n) pentru timp și O(1) pentru spațiu.
using System;namespace LeetCode.November{ public class ReverseLinkedListProb { public class ListNode { public int val; public ListNode next; public ListNode(int val = 0, ListNode next = null) { this.val = val; this.next = next; } } // Spațiu O(1) ; Timp O(n) public ListNode ReverseListIterative(ListNode head) { ListNode prev = null; while (head != null) { // salvează next var next = head.next; // next -> prev head.next = prev; // prev -> head prev = head; // head -> next head = next; } return prev; } // Spațiu O(n) ; Timp O(n) public ListNode ReverseListRecursion(ListNode head, ListNode prev) { if (head == null) { return prev; } var next = head.next; head.next = prev; return ReverseListRecursion(next, head); } public ListNode ReverseList(ListNode head) { var last = ReverseListIterative(head); return last; } public static void Test() { var problem = new ReverseLinkedListProb(); var r = problem.ReverseList(new ListNode(1, new ListNode(2, new ListNode(3)))); while (r != null) { Console.Write($"{r.val} "); r = r.next; } } }}Mulțumesc că ai citit!
