Jak znaleźć n-ty element na końcu listy pojedynczo połączonej?

Kluczem do tego algorytmu jest ustawienie dwóch wskaźników p1 i p2 osobno przez n-1 węzły, więc chcemy, aby p2 wskazywała na (n-1)th węzeł od początku listy, a następnie przesuwamy p2 aż osiągnie last węzeł listy. Gdy p2 osiągnie koniec listy p1 będzie wskazywał na n-ty węzeł z końca listy.

Umieściłem wyjaśnienie w linii jako komentarze. Mam nadzieję, że to pomoże:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

Alternatywnie możemy ustawić p1 i p2 osobno przez N węzłów zamiast z (n-1) a następnie przesuń p2 do końca listy zamiast przesuwać do ostatniego węzła:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;

Co sądzisz o tym podejściu.

1. Policz długość linkedlist.
2. rzeczywisty indeks węzła z głowy = długość linkedlist-podany indeks;
3. Napisz funkcję do travesre z head i pobierz węzeł z powyższego indeksu.

//this  is the recursive solution


//initial call
find(HEAD,k);

// main function
void find(struct link *temp,int k)
{  
 if( temp->next != NULL)
   find( temp->next, k);
 if((c++) == k)       // c is initially declared as 1 and k is the node to find from last.
  cout<<temp->num<<' ';
}

Jest tu już wiele odpowiedzi, ale wszystkie poruszają się po liście dwa razy (sekwencyjnie lub równolegle)lub używają dużo dodatkowej pamięci.

Możesz to zrobić podczas chodzenia po liście tylko raz (plus trochę) za pomocą stałej dodatkowej spacji:

Node *getNthFromEnd(Node *list, int n) {

    if (list == null || n<1) {
        return null; //no such element
    }

    Node *mark1 = list, *mark2 = list, *markend = list;
    int pos1 = 0, pos2 = 0, posend = 0;

    while (markend!=null) {
        if ((posend-pos2)>=(n-1)) {
            mark1=mark2;
            pos1=pos2;
            mark2=markend;
            pos2=posend;
        }
        markend=markend->next;
        ++posend;
    }
    if (posend<n) {
        return null; //not enough elements in the list
    }

    //mark1 and mark2 are n-1 elements apart, and the end is at least
    //1 element after mark2, so mark1 is at least n elements from the end

    while((posend - pos1) > n) {
      mark1 = mark1->next;
      ++pos1;
    }
    return mark1;
}

Ta wersja używa 2 dodatkowych wskaźników robi mniej niż N+n, Gdzie {[2] } jest długością listy, a n jest argumentem.

Jeśli użyjesz M dodatkowych wskaźników, możesz to obniżyć do N+ceil(n/(M-1)) (i powinieneś przechowuj je w okrągłym buforze)

Ponieważ brzmi to jak zadanie domowe, wolę pomóc ci pomóc sobie, zamiast dawać rzeczywiste rozwiązanie.

Sugeruję, abyś uruchomił ten kod na jakimś małym przykładowym zbiorze danych. Użyj debuggera, aby uruchamiać wiersze krok po kroku(możesz ustawić punkt przerwania na początku funkcji). To powinno dać ci wyobrażenie o tym, jak działa kod.

Możesz również Console.WriteLine() wypisać interesujące Cię zmienne.

Kolejne rozwiązanie tego problemu. Choć złożoność czasowa pozostaje taka sama, kod ten osiąga rozwiązanie w jednej pętli.

public Link findKthElementFromEnd(MyLinkedList linkedList, int k)
    {
        Link current = linkedList.getFirst();//current node
        Link currentK = linkedList.getFirst();//node at index k

        int counter = 0;

        while(current.getNext()!=null)
        {
            counter++;

            if(counter>=k)
            {
                currentK = currentK.getNext();
            }

            current = current.getNext();
        }

        //reached end
        return currentK;
    }

Po prostu odwróć linkowaną listę w czasie liniowym i znajdź element kth. Nadal działa w czasie liniowym.

Możesz po prostu przejść przez linkedlist i uzyskać rozmiar. Gdy już masz rozmiar, możesz znaleźć n ' termin w 2n, który nadal jest O(n).

public T nthToLast(int n) {
    // return null if linkedlist is empty
    if (head == null) return null;

    // declare placeholder where size of linkedlist will be stored
    // we are hoping that size of linkedlist is less than MAX of INT
    int size = 0;

    // This is O(n) for sure
    Node i = head;
    while (i.next != null) {
        size += 1;
        i = i.next;
    }

    // if user chose something outside the size of the linkedlist return null
    if (size < n)
        return null;

    // This is O(n) if n == size
    i = head;
    while(size > n) {
        size--;
        i = i.next;
    }

    // Time complexity = n + n = 2n
    // therefore O(n)

    return i.value;
}

Mam swoje rozwiązanie rekurencyjne w innym wątku w StackOverflow tutaj

No nie znasz długości linkedlist ... Będziesz musiał przejść raz, aby uzyskać długość likedlist, więc twoje podejście jest mało efektywne;

Bierzemy tutaj dwa wskaźniki pNode i qNode, oba początkowe punkty do head qNode. Następnie przemieszcza się do końca listy, a pNode przemieszcza się tylko wtedy, gdy różnica między liczeniem i pozycją jest większa niż 0, a pthNode zwiększa się raz w każdej pętli.

static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
    count++;
    if(count - pos > 0)
        pNode=pNode.next;
    qNode=qNode.next;
}
return pNode;
}

public int nthFromLast(int n){
    Node current = head;
    Node reference = head;      
    for(int i=0;i<n;i++){
        reference=reference.getNext();
    }
    while(reference != null){
        current = current.getNext();
        reference = reference.getNext();
    }
    return current.getData();
}

Użyj dwóch wskaźników pTemp i NthNode. Początkowo oba punkty wskazują na główny węzeł listy. NthNode zaczyna się poruszać dopiero po wykonaniu n ruchów przez pTemp. Od obu posunięć do przodu, aż pTemp osiągnie koniec listy. W rezultacie NthNode wskazuje na nth węzeł z końca połączonej listy.

public ListNode NthNodeFromEnd(int n){
    ListNode pTemp = head, NthNode = null;
   for(int count=1; count<n;count++){
     if(pTemp!=null){
       pTemp = pTemp.getNext();
     }
   }
   while(pTemp!=null){
     if(NthNode==null){
         NthNode = head;
     }
     else{
        NthNode = NthNode.getNext();
     }
     pTemp = pTemp.getNext();
   }
   if(NthNode!=null){
     NthNode = NthNode.getNext();
     return NthNode;
   }
return null;
}

Patrz podręcznik: "Struktura danych i algorytmy ułatwione w Javie"

Aby zrozumieć ten problem, powinniśmy zrobić prostą analogię z przykładem pomiaru. Powiedzmy, że musisz znaleźć miejsce ramienia, gdzie dokładnie 1 metr od środkowego palca, jak mierzysz? Wystarczy chwycić linijkę o długości 1 metra i umieścić górny koniec tej linijki na czubku środkowego palca, a dolny koniec miernika będzie dokładnie 1 metr od górnej części środkowego palca.

To co robimy w tym przykładzie będzie takie samo, po prostu potrzebujemy ramki o szerokości n-elementowej i musimy umieścić ramkę na końcu listy, tak więc węzeł startowy ramki będzie dokładnie N-tym elementem na końcu listy.

To jest nasza lista zakładając, że mamy Elementy M na liście, a nasza ramka z N elementem szerokim;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

<-- Frame -->

Potrzebujemy jednak tylko granic ramki, więc granica końcowa ramki będzie dokładnie (N-1) elementów od granicy początkowej ramki. Więc trzeba przechowywać tylko te granice żywioły. Nazwijmy je A i B;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

A <- N-Element Wide-> B

Pierwszą rzeczą jaką musimy zrobić jest znalezienie B, czyli końca klatki.

ListNode<T> b = head;
int count = 1;

while(count < n && b != null) {
    b = b.next;
    count++;
}

Teraz b jest N-tym elementem tablicy, a a znajduje się na głowie. Tak więc nasza ramka jest ustawiona, co zrobimy, to zwiększ oba węzły graniczne krok po kroku, aż b osiągnie koniec listy, gdzie a będzie n-th-do-ostatniego elementu;

ListNode<T> a = head;

while(b.next != null) {
    a = a.next;
    b = b.next;
}

return a;

Aby zebrać wszystko, a z Kontrola głowy, N

public ListNode<T> findNthToLast(int n) {
    if(head == null) {
        return null;
    } else {
        ListNode<T> b = head;
        int count = 1;

        while(count < n && b != null) {
            b = b.next;
            count++;
        }

        if(count == n && b!=null) {
            ListNode<T> a = head;

            while(b.next != null) {
                a = a.next;
                b = b.next;
            }

            return a;
        } else {
            System.out.print("N(" + n + ") must be equal or smaller then the size of the list");
            return null;
        }
    }
}

Możesz również rozwiązać powyższy problem używając tabel hash.Wpisy w tabeli hash to pozycja węzła i adres węzła. Więc jeśli chcemy znaleźć n-ty węzeł od końca (oznacza to m-n+1 Od pierwszego, gdzie M to liczba węzłów).Teraz, gdy wprowadzamy wpisy w tabeli hash otrzymujemy liczbę węzłów.Kroki to: -

1.Przemierzaj każdy węzeł i twórz odpowiednie wpisy w tabeli hash.

2.Poszukaj węzła m-n+1 w tabeli hash otrzymamy adres.

Złożoność czasu jest O (n).

Myślę, że jest jedna wada w kodzie pytań, i zastanawiam się, czy to zostało wzięte z książki, Jak to możliwe... może działać poprawnie, ale kod jest logicznie niepoprawny. Wewnątrz pętli for... warunek if powinien być sprawdzany pod kątem p2->next ! = NULL

 for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
       if (p2->next == null) {
       return null; // not found since list size < n
   }

...reszta jest w porządku i Wyjaśnienie jak podano już kod przesuwa p2 (n-1) pozycje przesuwają się do p1, Następnie w pętli while przesuwają je jednocześnie aż p2->next dotrze do końca .. fell free to tell if you find my odpowiedź Niepoprawna

Problem podany w książce Pucharu kariery jest nieco inny. Mówi, że znajdź n-ty ostatni element pojedynczo połączonej listy.

Oto Mój kod:

    public void findntolast(int index)
    {
        Node ptr = front; int count = 0;
        while(ptr!=null)
        {
            count++;
            if (count == index)
            {
                front = ptr;
                break;
            }
            ptr = ptr.next;
        }
        Node temp=front;
        while(temp!=null)
        {
            Console.WriteLine(temp.data);
            temp=temp.next;
        }
    }

Rozwiązanie rekurencyjne:

Node findKth (Node head, int count, int k) {
    if(head == null)
        return head;
    else {
        Node n =findKth(head.next,count,k);
        count++;

        if(count == k)
            return head;

        return n;
    }
}

Czy można użyć dodatkowej struktury danych .. jeśli tak, będzie to proste ... zacznij popychanie wszystkich węzłów do stosu, utrzymanie licznika pop go. jak na twój przykład, 8->10->5->7->2->1->5->4->10->10 zacznij czytać połączoną listę i zacznij przesuwać węzły lub węzeł - > dane na stos. więc stos będzie wyglądał jak Góra->{10, 10,4, 5, 1, 2, 7, 5, 10, 8}

Teraz zacznij wyskakiwać z góry stosu utrzymując licznik=1 i za każdym razem, gdy pop zwiększ licznik o 1, gdy dotrzyj do n-tego elementu (w twoim przykładzie 7-ty element).

Uwaga: spowoduje to wydrukowanie lub pobranie danych / węzłów w odwrotnej kolejności

Oto kod wykorzystujący podejście 2-wskaźnikowe: (Źródło )

Powolne i szybsze podejście wskaźnikowe

struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}

Rekurencja

node* findNthNode (node* head, int find, int& found){
    if(!head) {
        found = 1;
        return 0;
    }
    node* retval = findNthNode(head->next, find, found);
    if(found==find)
        retval = head;
    found = found + 1;
    return retval;
}

Moje podejście, to co myślę jest proste i ma złożoność czasową O (n).

Krok 1: Najpierw oblicz liczbę węzłów. Uruchom pętlę for rozpoczynającą się od pierwszego węzła do ostatniego węzła

Krok 2: Gdy już masz liczbę, zastosuj prostą matematykę, na przykład jeśli mamy znaleźć 7 węzeł do ostatniego węzła i liczba wszystkich węzłów wynosi 12, to (count - index)- 1 Da jakiś węzeł kth, do którego będziesz musiał przejść i będzie to n-ty węzeł do ostatniego węzła. W tym przypadku (12 -7) -1 = 4

Jeśli elementy są 8->10->5->7->2->1->5->4->10->10 następnie wynikiem jest 7. do ostatniego węzła jest 7, co jest niczym innym jak czwartym węzłem od początku.

W Javie użyję -

public class LL {
  Node head;
  int linksCount;

   LL(){
     head = new Node();
     linksCount = 0;
   }

  //TRAVERSE TO INDEX
  public Node getNodeAt(int index){
    Node temp= head;
    if(index > linksCount){
        System.out.println("index out of bound !");
        return null;
    }
    for(int i=0;i<index && (temp.getNext() != null);i++){
        temp = temp.getNext();
    }
    return temp.getNext();
  }
}

Nikt tutaj nie zauważył, że wersja Jonathana rzuci wyjątek NullPinterException, jeśli n jest większe niż długość LinkedList. Oto moja wersja:

public Node nth(int n){
        if(head == null || n < 1) return null;

        Node n1 = head;
        Node n2 = head;
        for(int i = 1; i < n; i++){
            if(n1.next == null) return null; 
            n1 = n1.next;
        }

        while (n1.next != null){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2;
}

Wprowadzam tylko małe zmiany: gdy node n1 wystąp do przodu, zamiast sprawdzać czy n1 jest null, sprawdzam pogodę n1.następnie jest null, albo w pętli while N1.następnie rzuci wyjątek NullPinterException.

Oto Wersja C# finding nth child z Linklist.

public Node GetNthLast(Node head, int n)
    {
        Node current, nth;
        current = nth = head;
        int counter = 0;

        while (current.next != null)
        {
            counter++;
            if (counter % n == 0)
            {
                for (var i = 0; i < n - 1; i++)
                {
                    nth = nth.next;
                }
            }
            current = current.next;
        }
        var remainingCounts = counter % n;
        for (var i = 0; i < remainingCounts; i++)
        {
            nth = nth.next;
        }
        return nth;
    }

W zależności od tolerancji kosztu pamięci (O (k) w tym rozwiązaniu) możemy przydzielić tablicę wskaźników o długości k i wypełnić ją węzłami jako okrągłą tablicę podczas przemierzania połączonej listy.

Kiedy skończymy przemierzać listę linkowaną, pierwszy element tablicy (pamiętaj tylko, aby poprawnie obliczyć indeks 0, ponieważ jest to tablica kołowa) będziemy mieli odpowiedź.

Jeśli pierwszy element tablicy jest null, nie ma rozwiązania naszego problemu.