LeetCodeシリーズの「反転チェーンテーブル」

剣指Offer 24.チェーンテーブルを反転
ListNode

// Definition for singly-linked list.
public class ListNode {
     
    int val;
    ListNode next;
    ListNode(int x) {
      
      	val = x; 
    }
}

一、反復解法:

class Solution {
     
    public ListNode reverseList(ListNode head) {
     
        if(head == null) return null;
      	//         
        ListNode cur = head;  
        ListNode pre = null;
      
        while(cur != null){
        
            ListNode nxt = cur.next;  // ①     cur      
            cur.next = pre;  // ②          ，       
            pre = cur;       // ③ pre cur     ，       pre
            cur = nxt;       // ④ 
        }
        return pre;
    }
}

反復解法は難しくなく、注意すべき点は2つあります.

仮想ノードを必要とせず、pre=nullでよい.

①②③④の順番は固定されています.

二、再帰解法:

class Solution {
     
    public ListNode reverseList(ListNode head) {
     
        if(head == null || head.next == null) return head;

        ListNode tmp = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return tmp;
    }
}

再帰的な問題の鍵を利用して、まずreverseList(ListNode head)という関数の役割を理解しなければならない.

頭のノードをください.私はこのチェーンテーブルを反転して、反転したチェーンテーブルの頭のノードに戻ることができます.

この関数の内部を考えないで、再帰的な問題を利用してすべてこのようにして、この関数を黒い箱として、それから3つのことを理解します:

私にこの関数を与えて、私はある機能を実現することができます

関数のパラメータは何ですか

関数は何を返しますか

次に、この黒い箱を使ってチェーンテーブルを反転し、チェーンテーブルのヘッドノードはheadです.
Node1/head
Node2
Node3
Node4/tail
null
ヘッダーにかかわらず、ListNode tmp = reverseList(head.next);という操作を実行すると何が起こるのでしょうか.

が起こりますnextノード(すなわちNode 2ノード)はヘッダノードのチェーンテーブルであり、後のノードのnextポインタが反転し、最終head.nextノードがテールノードとなり、

となる.

以下

Node 1/ヘッダノード
Node2
Node 4/末尾ノード
Node3
次の2つのステップを実行します.

head.next.next = head Node 2のnextノードをhead

に向ける.

head.next = null headのnextノードをnull

に向ける.
Node 4/末尾ノード
Node3
Node2
Node 1/ヘッダノード
null