Untitled
unknown
java
2 years ago
2.8 kB
3
Indexable
Never
Input : 23->28->28->35->49->49->53->53 (Time Complexity: O(n)) Output : 23->35 Kuna antud algoritm töötab ainult sorted linked listiga, sordime enne unsorted listi ja kasutame selleks MERGE SORTI (kõige väiksem complexity O(nlogn) ) /* The idea is to maintain a pointer (prev) to the node which just previous to the block of nodes we are checking for duplicates. In the first example, the pointer prev would point to 23 while we check for duplicates for node 28. Once we reach the last duplicate node with value 28 (name it current pointer), we can make the next field of prev node to be the next of current and update current=current.next. This would delete the block of nodes with value 28 which has duplicates. */ Ehk võtame kasutusele abimuutuja, mis viitab sellest nodest eelmisele nodele, mida parasjagu kontrollitakse korduste suhtes, ehk nt prev = 23 kuni kontrollime numbrit 28 (current), kui 28 on aint üks, liigutame kõiki pointereid edasi // Funktsioon mis esineb kõik numbri esinemised, kui neil on linked listis kordusi public void eemaldaKõikKorduvadNoded(juur) { // Loome abimuutuja, mis oleks juure koopia ja hoiaks endas listi juure algset väärtust (pointiks sellele) Node juureJälgija = new Node(null); // Dummy node points to the original head // Abinode viitab originaalsele juurele juureJälgija.next = juur; Node prev = juureJälgija; Node current = juur; // Käime listi läbi kuni jõuame lõppu while (current != null) { // Until the current and previous values // are same, keep updating curren // Kuni current ja currentist järgmise node väärtused on samad, uuenda iga loop currenti väärtust while (current.next != null && prev.next.val == current.next.val) { current = current.next; } // If current has unique value i.e current // is not updated, Move the prev pointer // to next node // Kui currentil on unikaalne väärtus, liigutame prev-i järgmisele nodele if (prev.next == current) prev = prev.next; // When current is updated to the last // duplicate value of that segment, make // prev the next of current*/ // Kui leitakse korduva väärtuse viimane esinemine, ühenda omavahel sellest blokist eelmine ja järgmine node, jättes kõik korduvad numbrid vahele else prev.next = current.next; current = current.next; } // Update original head to the next of dummy // node juur = juureJälgija.next; }