javaで隣接するノードを反転させる方法

Question

java初学者でLeetcodeで再帰の学習をしていますが、独学では理解が難しくご助言いただきたいです。

Swap Nodes in Pairs

Given 1->2->3->4, you should return the list as 2->1->4->3.

とあり、隣接する2つのノードを反転させる必要がありこの問題の回答が以下のようになっておりました。

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


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

これをリストが1->2->3->4の場合でトレースすると

ListNode n = head.next;　

でn=2、次に

head.next = swapPairs(head.next.next);

となっていて、この場合、head.next.nextは3->4なので

swapPairsを呼び出すとn = 4
その処理中のhead.next = swapPairs(head.next.next)ではhead.nextがnullになりheadの3が帰る
n.next = 3で、return でhead.nextに4->3が帰る

ここで初回の処理に戻り、

n.next = head = 1

ということだと思っているのですが、2->1->4->3という風に、

2->1と帰ってきた4->3が連結できる理由はhead.nextが4->3だからということでしょうか？

Answer 1

コードがあるのですから随所に表示を入れて実行してみると良いかと思います.

その処理中のhead.next = swapPairs(head.next.next)ではhead.nextがnullになりheadの3が帰る

head が 3 の場合 next.next は 4 の next なので ("head.nextがnull" ではなく) head が null じゃないでしょうか.

2->1と帰ってきた4->3が連結できる理由はhead.nextが4->3だからということ

そう書いてあります. 「head.next = swapPairs(略) 」

---

余談ですが, 『java初学者』でこんな再帰を学ぶ必要があるのかが疑問に思います.

Comments

[macaroni323]

ご回答いただきありがとうございました！

Answer 2

ノードを[val->next.val or null]のようにして表すと、
初期状態は
[1->2]->[2->3]->[3->4]->[4->null]
です。

最初の呼び出し(swap1と名付けます)でnは[2->3]のノードになります。
次にhead.next = swapPairs(head.next.next)の再帰呼び出し(swap2と名付けます)で
head = [3->4]で呼び出すので、nは[4->null]のノードになります。

swap2内でhead = nullで再帰呼び出しを行うので、swap2のhead.nextにはnullが返ります。
swap2のheadは[3->4]だったので、このnextがnullに書き換えられ、[3->null]になります。
そしてn.nextにheadが入るのですが、swap2ではnは[4->null],headは[3->4]改め[3->null]なので、
nが[4->3]となります。たぶんここまでは質問者様も正しく理解されていると思います。

この次は、swap2のnである[4->3]が呼び出し元に帰ります。
呼び出し元はswap1のhead.nextに代入するところで、headは[1->2]でした。
このnextが[4->3]のノードに書き換わるので、headは[1->4]になります。
最後にswap1のnのnextにheadが入ります。nが[2->3],headが[1->4]となるので、
nが[2->1]になります。

全部繋げると、
[2->1]->[1->4]->[4->3]->[3->null]
となります。

Comments

[macaroni323]

ご回答いただきありがとうございました！