webentwicklung-frage-antwort-db.com.de

Wie finde ich das n-te Element am Ende einer einfach verknüpften Liste?

Die folgende Funktion versucht, das nth to last - Element einer einfach verknüpften Liste zu finden.

Zum Beispiel: 

Wenn die Elemente 8->10->5->7->2->1->5->4->10->10 sind, lautet das Ergebnis 7th, und der letzte Knoten ist 7.

Kann mir jemand helfen, wie dieser Code funktioniert, oder gibt es einen besseren und einfacheren Ansatz?

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

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

  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}
59
Jony

Ihr Algorithmus funktioniert, indem Sie zunächst Verweise auf zwei Knoten in Ihrer verknüpften Liste erstellen, bei denen es sich um N Knoten handelt. Wenn also in Ihrem Beispiel N 7 ist, werden p1 auf 8 und p2 auf 4 gesetzt.

Es wird dann jede Knotenreferenz zum nächsten Knoten in der Liste vorrücken, bis p2 das letzte Element in der Liste erreicht. In Ihrem Beispiel ist dies wieder der Fall, wenn p1 5 und p2 10 ist. An diesem Punkt bezieht sich p1 auf das N-te bis letzte Element in der Liste (durch die Eigenschaft, dass sie N Knoten voneinander entfernt sind).

34
Eric

Der Schlüssel zu diesem Algorithmus besteht darin, zunächst zwei Zeiger p1 und p2 durch n-1-Knoten voneinander zu trennen, so dass p2 vom Anfang der Liste auf den (n-1)th-Knoten zeigen soll. Dann bewegen wir p2, bis er den last-Knoten der Liste erreicht. Sobald p2 das Ende der Liste erreicht, zeigt p1 vom Ende der Liste auf den n-ten Knoten.

Ich habe die Erklärung als Kommentar inline gestellt. Ich hoffe es hilft:

// 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;
 }

Alternativ können wir p1 und p2 um n Knoten anstelle von (n-1) auseinander setzen und dann p2 bis zum Ende der Liste verschieben, anstatt bis zum letzten Knoten zu gehen:

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;
62
codaddict

Was denkst du über diesen Ansatz?.

  1. Länge der verlinkten Liste zählen.
  2. Tatsächlicher Knotenindex aus head = Länge der verknüpften Liste - gegebener Index;
  3. Schreibe eine Funktion in den Travesre vom Kopf und nimm den Knoten am obigen Index.
9
Pritam Karmakar
//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<<' ';
}
7
dekontj

Hier gibt es bereits viele Antworten, die jedoch alle zweimal (entweder nacheinander oder parallel) durchlaufen werden oder viel zusätzlichen Speicherplatz benötigen.

Sie können dies tun, indem Sie die Liste nur einmal (und ein wenig) mit konstantem zusätzlichen Platz durchsuchen:

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;
}

Diese Version verwendet zwei zusätzliche Zeiger, die weniger als N+n-Traversierungen ausführen, wobei N die Länge der Liste und n das Argument ist.

Wenn Sie M-Zusatzzeiger verwenden, können Sie dies bis zu N+ceil(n/(M-1)) (und Sie sollten sie in einem Ringpuffer speichern)

3
Matt Timmermans

Da dies nach Hausaufgaben klingt, helfe ich Ihnen lieber, sich selbst zu helfen, anstatt eine wirkliche Lösung zu geben.

Ich schlage vor, dass Sie diesen Code in einem kleinen Beispieldatensatz ausführen. Verwenden Sie Ihren Debugger, um die Zeilen Schritt für Schritt auszuführen (Sie können einen Haltepunkt zu Beginn der Funktion festlegen). Dies sollte Ihnen eine Vorstellung davon geben, wie der Code funktioniert.

Sie können auch Console.WriteLine() zur Ausgabe von interessierenden Variablen verwenden.

2
mafu

Nur eine weitere Lösung für dieses Problem. Obwohl die zeitliche Komplexität gleich bleibt, erreicht dieser Code die Lösung in einer einzigen Schleife.

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;
    }
2
sunsin1985

Sie können einfach die verknüpfte Liste durchlaufen und die Größe ermitteln. Sobald Sie die Größe haben, können Sie den n-ten Term in 2n finden, der immer noch O(n) ist. 

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;
}
2
Y_Y

Lösung in C #. Erstellen Sie eine LinkedList mit Dummy-Werten.

  LinkedList<int> ll = new LinkedList<int>();
            ll.AddFirst(10);
            ll.AddLast(12);
            ll.AddLast(2);
            ll.AddLast(8);
            ll.AddLast(9);
            ll.AddLast(22);
            ll.AddLast(17);
            ll.AddLast(19);
            ll.AddLast(20);

Erstellen Sie 2 Zeiger p1 & p1, die auf den ersten Knoten zeigen.

        private static bool ReturnKthElement(LinkedList<int> ll, int k)
        {
            LinkedListNode<int> p1 = ll.First;
            LinkedListNode<int> p2 = ll.First;

Durchlaufen Sie die Schleife, bis entweder p2 Null ist - was bedeutet, dass die Länge der verknüpften Liste bis zum K-ten Element kleiner als das K-te Element OR ist

            for (int i = 0; i < k; i++)
            {
                p2 = p2.Next;
                if (p2 == null)
                {
                    Console.WriteLine($"Linkedlist is smaller than {k}th Element");
                    return false;
                }
            }

Nun iterieren Sie beide Zeiger, bis p2 null ist. Der im Zeiger p1 enthaltene Wert entspricht dem K-ten Element


            while (p2 != null)
            {
                p1 = p1.Next;
                p2 = p2.Next;
            }
            //p1 is the Kth Element
            Console.WriteLine($"Kth element is {p1.Value}");
            return true;
        }
2
VAT

Kehren Sie die verknüpfte Liste in linearer Zeit um und suchen Sie das k-te Element. Es läuft immer noch in linearer Zeit.

2
Nithin
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();
}
1
kaila88

Verwenden Sie zwei Zeiger pTemp und NthNode. Zunächst zeigen beide auf den Hauptknoten der Liste. NthNode beginnt sich erst zu bewegen, nachdem pTemp n Bewegungen ausgeführt hat. Von beiden geht es weiter, bis pTemp das Ende der Liste erreicht. Als Ergebnis zeigt NthNode vom Ende der verknüpften Liste auf den n-ten Knoten.

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;
}

Siehe TextBook: "Datenstruktur und Algorithmen in Java leicht gemacht"

1
Balasubramanian

Um dieses Problem zu verstehen, sollten wir eine einfache Analogie mit einem Messbeispiel durchführen. Nehmen wir an, Sie müssen die Stelle Ihres Arms finden, die genau einen Meter von Ihrem Mittelfinger entfernt ist. Wie würden Sie messen? Sie würden sich einfach ein Lineal von 1 Meter Länge schnappen und das obere Ende dieses Lineals an die Spitze Ihres Mittelfingers setzen, und das untere Ende des Messgeräts ist genau 1 Meter von der Oberseite Ihres Mittelfeldes entfernt. Finger.

Was wir in diesem Beispiel tun, ist dasselbe, wir brauchen nur einen Frame mit n-Element breit und wir müssen den Frame an das Ende der Liste setzen. Der Startknoten des Frames wird also genau n sein. th Element bis zum Ende der Liste.

Dies ist unsere Liste, vorausgesetzt wir haben M Elemente in der Liste und unseren Rahmen mit N Elementen breit;

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

<-- Frame -->

Wir brauchen jedoch nur die Grenzen des Frames, daher wird die Endgrenze des Frames genau (N-1) Elemente von der Startgrenze des Frames entfernt sein. So müssen nur diese Begrenzungselemente gespeichert werden. Nennen wir sie A und B;

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

A <- N-Element Wide-> B

Als erstes müssen wir B finden, das Ende des Frames. 

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

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

Nun ist b das n-te Element des Arrays und a befindet sich auf demKOPF. Unser Rahmen ist also festgelegt. Was wir tun werden, ist, beide Grenzknoten schrittweise zu inkrementieren, bis b bis zum Ende der Liste reicht, wo a das n-te-zum-letzten-Element ist.

ListNode<T> a = head;

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

return a;

Um alles zu sammeln, und mit den HEAD -Kontrollen prüft N <M (wobei M die Größe der Liste ist) und anderes Zeug. Hier ist die vollständige Lösungsmethode;

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;
        }
    }
}
1

Ich habe meine rekursive Lösung in einem anderen Thread in StackOverflow hier

1
sanjay

Nein, Sie kennen nicht die Länge der verlinkten Liste ... Sie müssen einmal durchgehen, um die Länge der beliebten Liste zu erhalten, so dass Ihr Ansatz wenig effizient ist.

1
CodeR

Wir nehmen hier zwei Zeiger pNode und qNode, beide Anfangspunkte auf den Kopf qNode. Fahren Sie dann bis zum Ende der Liste, und der pNode wird nur durchlaufen, wenn zwischen der Anzahl und der Position ein Unterschied besteht, der größer als 0 ist und der pthNode einmal in jeder Schleife erhöht wird.

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;
}
1
Rohit

Das Problem im Career Cup-Buch ist etwas anders. Es heißt, das vorletzte Element einer einzeln verknüpften Liste zu finden.

Hier ist mein Code:

    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;
        }
    }
0
Akshay

Rekursive Lösung:

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;
    }
}
0
Maher Rezeq

mein Ansatz ist meiner Meinung nach einfach und hat Zeitkomplexität O (n).

Schritt 1: Zuerst die Anzahl der Knoten ermitteln. Führen Sie eine for-Schleife aus, die vom ersten bis zum letzten Knoten beginnt

Schritt 2: Wenn Sie die Zählung haben, wenden Sie einfache Berechnungen an. Wenn zum Beispiel der letzte Knoten Knoten 7 gefunden hat und die Anzahl aller Knoten 12 beträgt, wird (count - index) - 1 einen k - ten Knoten geben, bis zu dem Sie müssen durchqueren und es ist der n-te Knoten zum letzten Knoten. In diesem Fall ist (12-7) -1 = 4

Wenn die Elemente 8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10 sind, ist das Ergebnis 7. bis letzter Knoten ist 7, was nichts anderes als der vierte Knoten ist der Anfang.

0
Dhananjaya HS

können Sie eine zusätzliche Datenstruktur verwenden? Wenn ja, wird es einfach ... Fangen Sie an, alle Knoten zu einem Stack zu verschieben, und halten Sie einen Zähler für einen Popup. 8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10 beginnen mit dem Lesen der verknüpften Liste und beginnen, die Knoten oder die Knoten-> Daten darauf zu verschieben ein Stapel. der Stapel sieht also wie oben aus -> {10, 10,4, 5, 1, 2, 7, 5, 10, 8} <- bottom.

beginnen Sie jetzt mit dem Poppen am oberen Rand des Stapels, wobei ein Zähler = 1 beibehalten wird. Erhöhen Sie den Zähler jedes Mal um 1, wenn Sie das n-te Element (in Ihrem Beispiel 7-Element) erreichen.

hinweis: Dadurch werden die Daten/Knoten in umgekehrter Reihenfolge gedruckt oder abgerufen

0
funnyCoder

Hier ist der Code mit dem 2-Zeiger-Ansatz: ( source )

Langsamer und schneller Zeigeransatz

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);
}


Rekursion

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;
}

0
kinshuk4

Hier ist die C # -Version des Findens des n-ten Kindes aus der Linkliste.

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;
    }
0
Shafqat Ali

Sie können das obige Problem auch mit Hashtabellen lösen. Die Einträge der Hashtabelle sind Position des Knotens und Adresse des Knotens. Wenn wir also den n-ten Knoten vom Ende aus finden wollen (dies bedeutet m-n + 1 vom ersten Punkt, wobei m die Anzahl der Knoten ist). Wenn wir nun die Hash-Tabelleneinträge eingeben, erhalten wir die Anzahl der Knoten. Schritte sind:

1.Verfahren Sie jeden Knoten und nehmen Sie entsprechende Einträge in der Hash-Tabelle vor.

2. Suchen Sie nach dem Knoten m-n + 1 in der Hashtabelle, wir erhalten die Adresse.

Zeitkomplexität ist O (n).

0
Shiv Shakti

Abhängig von der Speicherkostentoleranz (O (k) in dieser Lösung) könnten wir ein Array von Zeigern der Länge k zuweisen und es mit den Knoten als kreisförmiges Array füllen, während Sie die verknüpfte Liste durchlaufen. 

Wenn wir die verknüpfte Liste durchlaufen haben, das erste Element des Arrays (stellen Sie sicher, dass Sie den 0-Index korrekt berechnen, da es sich um ein kreisförmiges Array handelt), haben wir die Antwort.

Wenn das erste Element des Arrays null ist, gibt es keine Lösung für unser Problem.

0

Ich denke, es gibt einen Fehler im Fragencode, und ich frage mich, ob er aus einem Buch stammt, wie dies möglich ist ... er wird zwar korrekt ausgeführt, der Code ist jedoch etwas logisch nicht korrekt. Innerhalb der for-Schleife ... sollte die if-Bedingung gegen p2->next ! = NULL geprüft werden.

 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
   }

... rest ist in Ordnung und Erklärung, da der Code bereits verschoben ist, verschiebt sich der Code p2(n-1) um p1, dann bewegen Sie sie in der Schleife gleichzeitig, bis p2->next das Ende erreicht hat

0
user1107108

Zuerst

Wie schon erwähnt, aber um es klarer zu sagen: Die Frage stammt von

<Cracking the coding interview 6th> | IX Interview Questions | 2. Linked Lists | Question 2.2.

Es ist ein großartiges Buch von Gayle Laakmann McDowell, einem Software-Ingenieur von Google, der viele Leute interviewt hat.


Ansätze

(Wenn die verknüpfte Liste die Länge nicht verfolgt), gibt es zwei Ansätze in O(n) time und O(1) Platz:

  • Suchen Sie zuerst die Länge, und führen Sie eine Schleife zum Element (len-k + 1) aus.
    Diese Lösung wird in dem Buch nicht erwähnt, wie ich mich erinnere.
  • Führen Sie über den Zeiger 2 eine Schleife aus, und halten Sie sie (k-1) auf Abstand.
    Diese Lösung stammt aus dem Buch, ebenso wie in der Frage.

Code

Es folgt die Implementierung in Java mit Unit-Test (ohne Verwendung einer erweiterten Datenstruktur in JDK selbst).

KthToEnd.Java

/**
 * Find k-th element to end of singly linked list, whose size unknown,
 * <p>1-th is the last, 2-th is the one before last,
 *
 * @author eric
 * @date 1/21/19 4:41 PM
 */
public class KthToEnd {
    /**
     * Find the k-th to end element, by find length first.
     *
     * @param head
     * @param k
     * @return
     */
    public static Integer kthToEndViaLen(LinkedListNode<Integer> head, int k) {
        int len = head.getCount(); // find length,

        if (len < k) return null; // not enough element,

        return (Integer) head.getKth(len - k).value; // get target element with its position calculated,
    }

    /**
     * Find the k-th to end element, via 2 pinter that has (k-1) distance.
     *
     * @param head
     * @param k
     * @return
     */
    public static Integer kthToEndVia2Pointer(LinkedListNode<Integer> head, int k) {
        LinkedListNode<Integer> p0 = head; // begin at 0-th element,
        LinkedListNode<Integer> p1 = head.getKth(k - 1); // begin at (k-1)-th element,

        while (p1.next != null) {
            p0 = p0.next;
            p1 = p1.next;
        }

        return p0.value;
    }

    static class LinkedListNode<T> {
        private T value;
        private LinkedListNode next;

        public LinkedListNode(T value) {
            this.value = value;
        }

        /**
         * Append a new node to end.
         *
         * @param value
         * @return new node
         */
        public LinkedListNode append(T value) {
            LinkedListNode end = getEnd();
            end.next = new LinkedListNode(value);
            return end.next;
        }

        /**
         * Append a range of number, range [start, end).
         *
         * @param start included,
         * @param end   excluded,
         */
        public void appendRangeNum(Integer start, Integer end) {
            KthToEnd.LinkedListNode last = getEnd();
            for (int i = start; i < end; i++) {
                last = last.append(i);
            }
        }

        /**
         * Get end element of the linked list this node belongs to, time complexity: O(n).
         *
         * @return
         */
        public LinkedListNode getEnd() {
            LinkedListNode end = this;
            while (end != null && end.next != null) {
                end = end.next;
            }

            return end;
        }

        /**
         * Count of element, with this as head of linked list.
         *
         * @return
         */
        public int getCount() {
            LinkedListNode end = this;
            int count = 0;
            while (end != null) {
                count++;
                end = end.next;
            }

            return count;
        }

        /**
         * Get k-th element from beginning, k start from 0.
         *
         * @param k
         * @return
         */
        public LinkedListNode getKth(int k) {
            LinkedListNode<T> target = this;
            while (k-- > 0) {
                target = target.next;
            }

            return target;
        }
    }
}

KthToEndTest.Java

(Unit-Test mit TestNG, oder Sie wechseln nach Wunsch zu JUnit/..)

import org.testng.Assert;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;

/**
 * KthToEnd test.
 *
 * @author eric
 * @date 1/21/19 5:20 PM
 */
public class KthToEndTest {
    private int len = 10;
    private KthToEnd.LinkedListNode<Integer> head;

    @BeforeClass
    public void prepare() {
        // prepare linked list with value [0, len-1],
        head = new KthToEnd.LinkedListNode(0);
        head.appendRangeNum(1, len);
    }

    @Test
    public void testKthToEndViaLen() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndViaLen(head, i).intValue(), len - i);
        }
    }

    @Test
    public void testKthToEndVia2Pointer() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head, i).intValue(), len - i);
        }
    }
}

Tipps:

  • KthToEnd.LinkedListNode
    Es handelt sich um einen einfachen, einfach verknüpften Listenknoten, der von Grund auf implementiert wird, und stellt einen verknüpften Listenstart dar.
    Es verfolgt nicht zusätzlich Kopf/Schwanz/Länge, obwohl es Methoden dafür gibt.
0
Eric Wang

In Java werde ich verwenden- 

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();
  }
}
0
Manisha

Niemand hat hier bemerkt, dass Jonathans Version eine NullPinterException auslöst, wenn n größer ist als Länge von LinkedList . Hier ist meine Version:

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;
}

Ich mache hier nur eine kleine Änderung: Wenn der Knoten n1 vorwärts geht, anstatt zu prüfen, ob n1 null ist, überprüfe ich, ob Wetter n1.next null ist, oder in while, während die Schleife n1.next eine NullPinterException auslöst.

0
sofia