技術共有

選択されたリコウ、ニューケリアン表面テストの質問

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

💎 欢迎各位大佬互三：私のホームページ

1. 逆リンクリスト

206.逆リンクリスト

考察: 追加のスペースを空けず、元のリンク リストのみを変更する場合、どのような方法を使用する必要がありますか?

2 番目の要素から開始して、順番にヘッド挿入を実行するだけです。

次に、参照を変更し、最後の要素を null にポイントするだけです。

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         //head为null，直接返回
  4.         if(head == null){
  5.             return head;
  6.         }
  7.  
  8.         ListNode cur = head.next;
  9.         //head变为了末尾元素，指向null
  10.         head.next = null;
  11.         while(cur!=null){
  12.             //curn为cur的next节点，便于往后移动
  13.             ListNode curn = cur.next;    
  14.             cur.next = head;
  15.             head = cur;
  16.             //更新cur
  17.             cur = curn;
  18.         }
  19.         return head;
  20.     }
  21. }

2. リンクリストの中間ノード

876. リンクリストの中間ノード

この質問に対して最初に思い浮かぶ方法は、間違いなく cnt を定義し、リンクされたリストを 1 回走査し、次に中央の数値を見つけて、戻り値を走査することです。この方法は非常に簡単ですが、中間ノードを見つけるためにリンクリストを一度だけ使用しますか?

これは新しいアイデアです。高速ポインタと低速ポインタを使用して、先頭から開始します。高速ポインタは毎回 2 つのノードを移動し、低速ポインタは毎回 1 つのノードを移動します。これで最終的な目標は達成されますか?

それでは、それを実装してみましょう:

  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         if(head == null){
  4.             return null;
  5.         }
  6.         ListNode fast = head;
  7.         ListNode slow = head;
  8.         while(fast!= null&&fast.next!= null){
  9.             fast = fast.next.next;
  10.             slow = slow.next;
  11.         }
  12.         return slow;
  13.     }
  14. }

これはより効率的でしょうか?

3. 最後のノードから k 番目のノードを返します。

インタビューの質問 02.02. 最後から k 番目のノードを返します。

この質問で最初に思い浮かぶのは、一度走査して全長を取得し、最後から k 番目のノードを見つけることです。ただし、前の質問に基づいて、別の方法を考えることができます。同様に、fast ポインタと low ポインタを使用して、最初に fast go k-1 ノードを実行し、その後、slow と fast go を同時に実行します。fast の次が null の場合、fast が最後のノードに到達し、この時点で low が実行されることを意味します。は下から k 番目のノードです。

この質問は、入力 k が正当であることを示しているため、追加の判断は必要ありません。k が不正であるかどうかを判断する方法は、リンクされたリストの長さを直接求めることができないため、slow が歩きながら判断する必要があります。

  1. class Solution {
  2.     public int kthToLast(ListNode head, int k) {
  3.         if (head == null) {
  4.             return -1;
  5.         }
  6.         ListNode fast = head;
  7.         ListNode slow = head;
  8.         int cnt = 0;
  9.         while (cnt != k - 1) {
  10.             //判断k的合法性，虽然本题不用判断
  11.             fast = fast.next;
  12.             if(fast == null){
  13.                 return;
  14.             }
  15.             cnt++;
  16.         }
  17.         //slow和fast同时移动
  18.  
  19.         while (fast.next != null) {
  20.             fast = fast.next;
  21.             slow = slow.next;
  22.         }
  23.         return slow.val;
  24.     }
  25. }

4. リンクされたリストを結合する

21. 2 つの順序付きリンク リストを結合する

アイデア：新しいノード newH を定義し、headA と headB の値を比較するだけで、マージされたリンク リストのヘッド ノードを最終的に見つけることができます。また、tmp = newH を定義し、小さい方のノードを定義する必要もあります。 tmp.next がそれを指します。

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  3.         ListNode head = new ListNode();
  4.         ListNode tmp = head;
  5.     
  6.         while(list1!=null&&list2!=null){
  7.             if(list1.val < list2.val){
  8.                 tmp.next = list1;
  9.                 list1 = list1.next;
  10.                 tmp = tmp.next;
  11.             }else{
  12.                 tmp.next = list2;
  13.                 list2 = list2.next;
  14.                 tmp = tmp.next;
  15.             }
  16.         }
  17.         //判断剩余的情况
  18.         if(list1!=null){
  19.             tmp.next = list1;
  20.         }else if(list2!=null){
  21.             tmp.next = list2;
  22.         }
  23.         return head.next;
  24.     }
  25. }

5. リンクされたリストの分割

CM11 リンクリスト分割

これはニウケのインタビューの質問です。質問の意味は、x の左側が x より小さく、右側が x より大きいです。元の順序は変更できません。

アイデア: 元のリンク リストを横断する新しいノード cur を定義し (元のリンク リストが変更されないようにするため)、x より大きいものをすべてリンク リストに入れ、x より小さいものをすべてリンク リストに入れ、最後に 2 つを接続します。リンクされたリスト。

  1. public class Partition {
  2.     public ListNode partition(ListNode pHead, int x) {
  3.         ListNode bs = null;
  4.         ListNode be = null;
  5.         ListNode as = null;
  6.         ListNode ae = null;
  7.         ListNode cur = pHead;
  8.         while (cur != null) {
  9.             if (cur.val < x) {
  10.                 //处理刚开始为null的情况
  11.                 if (bs == null) {
  12.                     bs = be = cur;
  13.                 }else{
  14.                     be.next = cur;
  15.                     be = be.next;
  16.                 }
  17.             }else{
  18.                 if(as == null){
  19.                     as = ae = cur;
  20.                 }else{
  21.                     ae.next = cur;
  22.                     ae = ae.next;
  23.                 }
  24.             }
  25.             cur = cur.next;
  26.         }
  27.         //都是比x大的情况
  28.         if(bs == null){
  29.             return as;
  30.         }
  31.         be.next = as;
  32.         //最后都要置为null，不然可能会报错
  33.         if(as!=null){
  34.             ae.next = null;
  35.         }
  36.         return bs;
  37.     }
  38. }

それらが x より大きい場合、つまり bs = null の場合、as が直接返され、as.next が最終的に null に設定される場合に注意してください。

6. OR36連結リストの回文構造

OR36 連結リストの回文構造

これは Niuke からの質問です。時間計算量と空間計算量の要件があるため、追加の配列を開くことはできません。そうしないと空間計算量が克服されず、通常の走査の計算量は O(n) になります。

考え方は次のとおりです。まず、リンクされたリストの中央の遅いノードを見つけ、次に先頭のノードを逆方向に走査し、遅いノードも逆方向に走査します。値が異なるということは、テキスト構造が返されていないことを意味します。

リンクされたリストを逆にして中間ノードを見つけることは以前にも行われていました。

  1. public class PalindromeList {
  2.     public boolean chkPalindrome(ListNode head) {
  3.         if (head == null) {
  4.             return true;
  5.         }
  6.         //找到中间节点
  7.         ListNode fast = head;
  8.         ListNode slow = head;
  9.         while (fast != null && fast.next != null) {
  10.             fast = fast.next.next;
  11.             slow = slow.next;
  12.         }
  13.         //从slow开始到末尾反转
  14.         ListNode cur = slow.next;
  15.         while (cur != null) {
  16.             ListNode curn = cur.next;
  17.             cur.next = slow;
  18.             slow = cur;
  19.             cur = curn;
  20.         }
  21.         //判断回文
  22.         while (head != slow) {
  23.             if (head.val != slow.val) {
  24.                 return false;
  25.             }
  26.             //判断偶数节点
  27.             if (head.next == slow) {
  28.                 return true;
  29.             }
  30.             head = head.next;
  31.             slow = slow.next;
  32.         }
  33.         return true;
  34.     }
  35. }

なお、奇数ノードのリンクリストと偶数ノードのリンクリストの判定にも違いがある。

偶数ノードを先頭に移動すると無限ループが発生するため、偶数ノードについては追加の判定が必要となります。

7. 交差リンクリスト

160. 交差リンクリスト

図に示すように、交差するリンク リストは「Y」と同様の変換です。

以下の質問の写真も非常に鮮明です。

アイデア: A が短いか B が短いかに関係なく、それらの間の違いは交差前の部分であるため、長いリンク リストを差分だけ移動するだけで、2 つのリンク リストのノードが同時に後方に移動します。同一のノードが次のノードと交差します。

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         ListNode pl = headA;
  4.         ListNode ps = headB;
  5.         int cnta = 0,cntb = 0;
  6.         //计算两个链表的长度
  7.         while(pl!=null){
  8.             pl = pl.next;
  9.             cnta++;
  10.         }
  11.         while(ps!=null){
  12.             ps = ps.next;
  13.             cntb++;
  14.         }
  15.         //如果链表b长，就更新pl,ps
  16.         int len = cnta - cntb;
  17.         //上面求长度时pl,ps都为空了，所以这里再重新指向
  18.         pl = headA;
  19.         ps = headB;
  20.         if(len < 0){
  21.             pl = headB;
  22.             ps = headA;
  23.             len = cntb - cnta;
  24.         }
  25.         //移动差值
  26.         while(len!=0){
  27.             pl = pl.next;
  28.             len--;
  29.         }
  30.         //找到相交节点
  31.         while(pl!=ps){
  32.             pl = pl.next;
  33.             ps = ps.next;
  34.         }
  35.         //链表不相交的情况
  36.         if(pl == null) return null;
  37.         return pl;
  38.     }
  39. }

最後に、素の状況を追加する必要があります。この質問は追加しなくても合格できますが、厳密さを期すために追加する必要があります。

8. 循環リンクリスト

8.1 ループがあるかどうかを判断する

141. 循環リンクリスト

リンクされたリストに循環があるかどうかを判断する方法:まだスピードポインタを使用して、2人が遊び場で走っているように、1人は速く走り、もう1人はゆっくりと走ります。このとき、速い人は遅い人を確実に超えることができます。 , しかし、環がいなかったら、どんなに追いかけても捕まえられない女神のように、出会うことはできなかったでしょう。

ただし、2 つのノードを持つリングで、定義された高速ポインターが一度に 3 ステップを実行し、低速ポインターが一度に 1 ステップを実行する場合、それらは決して一致しません。

したがって、定義されたポインタは、一方が 2 歩、もう一方が 1 歩であれば、必ず一致することを判断する必要があります。

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         while(fast!=null&&fast.next!=null){
  6.             fast = fast.next.next;
  7.             slow = slow.next;
  8.             if(fast == slow) return true;
  9.         }
  10.         return false;
  11.     }
  12. }

8.2 ノードをリング入口に戻す

142. 循環リンクリスト II

今度は、前の質問でリングであるかどうかを判断した後、リングへの進入点を見つける必要があります。次のような推論ができます。

  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         //判断环
  6.         while(fast!=null&&fast.next!=null){
  7.             fast = fast.next.next;
  8.             slow = slow.next;
  9.             if(fast == slow) break;
  10.         }
  11.         if(fast == null||fast.next == null) return null;
  12.         slow = head;
  13.         //寻找环
  14.         while(slow!=fast){
  15.             slow = slow.next;
  16.             fast = fast.next;
  17.         }
  18.         return slow;
  19.     }
  20. }

追加する必要があるのは次のとおりです。

リングが非常に小さい場合、最終的な単純化結果は上記のようになりますが、元のコードはまだ問題ありません。

個人プロフィール

彼は 30 年以上テクノロジーの研究に専念しており、java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。

私の連絡先情報

郵便