Java は、リンク リストの最後から k 番目のノードを出力するためのサンプル コード共有を実装します。

この記事では、Java 出力のリンク リストの下から k 番目のノードに関連する内容を主に紹介します。これには 3 つの設計アイデアとコード例が含まれており、必要な方はそれについて学ぶことができます。

問題の説明

リンクリストを入力し、リンクリストの最後からk番目のノードを出力します。 (末尾のノードが最後のノードです) ノードの定義は次のとおりです:

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

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

アイデア 1:

まずリンクされたリストを走査し、その長さを計算します 次に、下から k 番目のノードを計算します。は正の長さ - k + 1 です。 最後に、リンク リストを走査して目的のノードを見つけます

時間計算量は O(2n) で、リンク リストを 2 回走査する必要があります

コードは次のとおりです:

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

アイデア 2:

リンクされたリストを 1 回だけ走査するだけで取得できることを期待します。 2 つのポインターを設定します。1 つは最初のノードを指すように初期化され、2 つ目は k 番目のノードを指すように初期化されます。次に、2 つのポインターが同期して後方に移動し、2 番目のポインターが末尾ノードを指すと、最初のポインターは下から k 番目のノードを指します。 リンクリストを逆にすると、元の問題は正の k 番目のノードを見つけることになります。

ただし、これは元のリンク リストを変更し、アイデア 2 よりも効率的ではありません

リンク リストの逆: 「逆リンク リストの Java 言語実装のコード例」を参照してください

概要

以上がJava は、リンク リストの最後から k 番目のノードを出力するためのサンプル コード共有を実装します。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。