Java implémente le partage d'exemples de code pour afficher le k-ième nœud à partir du bas d'une liste chaînée

Cet article présente principalement le contenu pertinent du kième nœud du bas de la liste des liens de sortie Java. Il implique trois idées de conception et des exemples de code. Il a une certaine valeur de référence et les amis dans le besoin peuvent en apprendre davantage.

Description du problème

Entrez une liste chaînée et affichez le k-ème nœud du dernier de la liste chaînée. (Le dernier nœud est le dernier)

Le nœud est défini comme suit :

public class ListNode {
  int val;
  ListNode next = null;

  ListNode(int val) {
    this.val = val;
  }
}

Idée 1 :

Parcourez d'abord la liste chaînée et calculez sa longueur
Ensuite, calculez que le kième nœud du dernier est la longueur positive - k + 1.
Enfin parcourez la liste chaînée ; et trouvez La complexité temporelle du nœud demandé
est O(2n), et la liste chaînée doit être parcourue deux fois

Le code est le suivant : <.>

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    int length = 1;
    while(p.next != null){
      length++;
      p = p.next;
    }
    int index = length - k + 1;
    if(index <= 0){
      return null;
    }
    p = head;
    int num = 1;
    while(p.next != null && num < index){
      num++;
      p = p.next;
    }
    if(num < index){
      return null;
    }else{
      return p;
    }
  }

Idée 2 :

Attendez-vous à l'obtenir en parcourant la liste chaînée une seule fois.

Définissez deux pointeurs, l'un initialisé pour pointer vers le premier nœud et le second vers le k-ème nœud. Ensuite, les deux pointeurs reculent de manière synchrone. Lorsque le deuxième pointeur pointe vers le nœud de queue, le premier pointeur pointe vers le k-ième nœud à partir du bas

Code :

public ListNode FindKthToTail(ListNode head,int k) {
    if(head == null || k <= 0){
      return null;
    }
    //直接遍历
    ListNode p = head;
    ListNode q = head;
    for(int i = 0; i < k-1; i++){
      if(q == null){
        return null;
      }
      q = q.next;
    }
    if(q == null){
      return null;
    }
    while(q.next != null){
      p = p.next;
      q = q.next;
    }
    return p;
  }

Idée 3 :

Inversez la liste chaînée, puis le problème d'origine devient la recherche du kième point de nœud positif.

Cependant, cela modifie la liste chaînée d'origine et n'est pas plus efficace que l'idée 2

Inversion de la liste chaînée : reportez-vous à "Implémentation en langage Java de l'exemple de code de liste chaînée inversée"

Résumé

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!