逆リンクリストを実装する Java コード例

この記事では、Java 言語で逆リンク リストを実装するコード例を主に紹介します。編集者は、それを必要とする友人の参考のためにここで共有します。

問題の説明

連結リストの先頭ノードを入力し、連結リストを反転し、反転した連結リストの先頭ノードを出力する関数を定義します。リンク リストのノードは次のとおりです:

public class ListNode {
  int val;
  ListNode next = null;
  ListNode(int val) {
    this.val = val;
  }
}

アイデア 1:

リンク リストを逆にするには、ノード i について、次のノードをその先行ノードを指す必要があるため、先行ノードを保存する必要があります。同時に、i の次を再割り当てすると、i の後継者を見つけることができなくなります。そのため、再割り当てする前に i の後継者を保存する必要があります。

コード:

public ListNode ReverseList(ListNode head) {
    if(head == null){
      return null;
    }
    ListNode rHead = null;
    ListNode prior = null;//store prior
    ListNode q = head;//store current
    while(q != null){
      ListNode next = q.next;//store the next
      if(next == null){
        rHead = q;
      }
      q.next = prior;
      prior = q;
      q = next;
    }
    return rHead;
  }

アイデア2:

再帰のアイデアを使用します(再帰を使用する場合、毎回次のようにする必要があるため、まだ考えていません)リンクされたリスト

概要

以上が逆リンクリストを実装する Java コード例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。