[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を変更することがこの問題の主な目的だと思います.でも難しすぎて、本を読んで理解するのに時間がかかりました.
解決策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
  • 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]
  • 上のコードを見て、最初は理解できないところがありました.start.next.next = tmpのとき、tmpは[2,3,4,5]で、真ん中の3がなくなってしまいましたが、なぜ[1,3,2,4,5]になったのかと思います.
  • end.next=end.next.next構文でtmpを変更します.
    ステップ1end.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の変更に伴い、ノードに含まれる他のすべての内容が変更されるため、より混同される可能性があります.
    リファレンス
  • 本:Pythonアルゴリズムインタビュー