質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

Q&A

解決済

2回答

908閲覧

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

macaroni323

総合スコア31

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

0グッド

0クリップ

投稿2019/11/04 03:46

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

Swap Nodes in Pairs

example

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

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

java

1/** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 10 11public class Solution { 12 public ListNode swapPairs(ListNode head) { 13 if ((head == null)||(head.next == null)) 14 return head; 15 ListNode n = head.next; 16 head.next = swapPairs(head.next.next); 17 n.next = head; 18 return n; 19 } 20}

これをリストが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だからということでしょうか?

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

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

その処理中の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初学者』でこんな再帰を学ぶ必要があるのかが疑問に思います.

投稿2019/11/04 04:18

jimbe

総合スコア12543

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

macaroni323

2019/11/04 06:53

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

0

ベストアンサー

ノードを[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]
となります。

投稿2019/11/04 04:16

編集2019/11/04 04:19
swordone

総合スコア20649

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

macaroni323

2019/11/04 06:53

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問