[leetcode][JS]Reverse Linked List II
Reverse Linked List II
質問:https://leetcode.com/problems/reverse-linked-list-ii/
LinkedList:ノードが与えられたタイミングでのみm,n間のLinkedListが反転する問題である.
この問題を解くのは難しくないかもしれない.これらの値を配列として持ってきて,それを逆方向にしてLinkedListとすればよい.
しかし、新しいListNodeオブジェクトを作成して貼り付けるのはあまり解決策ではないと思います.
現在のオブジェクトのnextを変更することがこの問題の主な目的だと思います.でも難しすぎて、本を読んで理解するのに時間がかかりました.
解決策
上の
ex) 1-2-3-4-5 tmp: [2,3,4,5]
start: [1,3,4,5]
end: [2,4,5]
start: [1,3,2,4,5] tmp: [3,2,4,5]
start: [1,4,5]
end: [2,5]
start: [1,4,3,2,5] 上のコードを見て、最初は理解できないところがありました.
ステップ1
ステップ2
tmp:[3,2,4,5]経由
つまり.
以上の4つのプロセスをすべて変更するまで繰り返します.
code
実は私もよく言えません.tmpにendがあり、endがtmpに変更された場合...これらをどのように計算してコードを書くか分かりません.
並べ替えて解くのは簡単ですが、インタビューでそう言うのは期待の方向ではないので、上記のようにリンクリストを偽造する方法で解決したほうがいいと本では言っています.
配列とは異なり、nextの変更に伴い、ノードに含まれる他のすべての内容が変更されるため、より混同される可能性があります.
リファレンス本:Pythonアルゴリズムインタビュー
質問:https://leetcode.com/problems/reverse-linked-list-ii/
LinkedList:ノードが与えられたタイミングでのみm,n間のLinkedListが反転する問題である.
この問題を解くのは難しくないかもしれない.これらの値を配列として持ってきて,それを逆方向にしてLinkedListとすればよい.
しかし、新しいListNodeオブジェクトを作成して貼り付けるのはあまり解決策ではないと思います.
現在のオブジェクトのnextを変更することがこの問題の主な目的だと思います.でも難しすぎて、本を読んで理解するのに時間がかかりました.
解決策
start
:逆起動前のnodeend
:初期start.next終了点ではendの後ろに逆方向にできないノードがあります.start
およびend
は変更されません.(next部分を変更するだけで順序を変更できます.)上の
start
,end
の設定が完了すると、次の繰り返しはm~nに開始する.tmp = start.next;
start.next = end.next;
end.next = end.next.next;
start.next.next = tmp;
例を試してみます.ex) 1-2-3-4-5
start: [1,3,4,5]
end: [2,4,5]
start: [1,3,2,4,5]
start: [1,4,5]
end: [2,5]
start: [1,4,3,2,5]
start.next.next = tmp
のとき、tmp
は[2,3,4,5]で、真ん中の3がなくなってしまいましたが、なぜ[1,3,2,4,5]になったのかと思います.end.next=end.next.next
構文でtmpを変更します.ステップ1
end.next=end.next.next
このセクションでは、end:[2,3,4,5]=>end:[2,4,5]となり、tmp:[2,3,4,5]=>tmp:[2,4,5]となる.ステップ2
tmp:[3,2,4,5]経由
end.next=end.next.next
:end:[2,4,5]=>end:[2,5]、tmp:[3,2,4,5]=>tmp:[3,2,5]start:[1,4,3,3,3,2,5].tmp=start.next
-tempはstartの次の部分の並べ替えに使用されます.start.next = end.next
-startの後ろにendの後ろに続く数字end.next = end.next.next
-startの後に設定されたend.次です.に変更start.next.next = tmp
-startはstart-endです.next-tmpに設定します.以上の4つのプロセスをすべて変更するまで繰り返します.
code
const reverseBetween = (node, m, n) => {
if (!node || m === n) return node;
const head = new ListNode();
let start = head;
head.next = node;
for (let i = 1; i < m; i++) {
start = start.next;
}
let end = start.next;
let tmp = null;
for (let i = m; i < n; i++) {
tmp = start.next;
start.next = end.next;
end.next = end.next.next;
start.next.next = tmp;
}
return head.next;
};
の最後の部分実は私もよく言えません.tmpにendがあり、endがtmpに変更された場合...これらをどのように計算してコードを書くか分かりません.
並べ替えて解くのは簡単ですが、インタビューでそう言うのは期待の方向ではないので、上記のようにリンクリストを偽造する方法で解決したほうがいいと本では言っています.
配列とは異なり、nextの変更に伴い、ノードに含まれる他のすべての内容が変更されるため、より混同される可能性があります.
リファレンス
Reference
この問題について([leetcode][JS]Reverse Linked List II), 我々は、より多くの情報をここで見つけました https://velog.io/@proshy/leetcodeJSReverse-Linked-List-IIテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol