기술나눔

선정된 Likou, Niukelian 표면 테스트 문제

2024-07-12

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

💎 欢迎各位大佬互三：내 홈페이지

1. 역방향 연결리스트

206.역방향 연결리스트

생각하기: 추가 공간을 열지 않고 원본 연결 리스트만 수정한다면 어떤 방법을 사용해야 할까요?

두 번째 요소부터 시작하여 순서대로 헤드 삽입을 수행하면 됩니다.

그런 다음 참조를 수정하고 마지막 요소를 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. 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번째 노드를 찾는 것입니다. 그러나 이전 질문을 기반으로 다른 방법을 생각해 볼 수 있습니다. 비슷하게,빠른 포인터와 느린 포인터를 사용하여 k-1개 노드를 먼저 빠르게 이동시킨 다음 동시에 빠른 속도의 다음이 null이면 빠른 속도가 마지막 노드에 도달했음을 의미하고 이때는 느려집니다. 아래에서 k번째 노드입니다.

이 질문은 입력 k가 적법하므로 추가 판단이 필요하지 않음을 나타냅니다. k가 불법인지 판단하는 방법과 연결된 목록의 길이를 직접 찾을 수 없으므로 천천히 판단해야 합니다.

  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. 두 개의 순서 연결 리스트 병합

아이디어:새로운 노드 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 연결리스트 분할

Niuke의 인터뷰 질문입니다. 질문의 의미는 연결된 목록을 나누는 것입니다. x의 왼쪽은 x보다 작고 오른쪽은 x보다 큽니다.

아이디어: 원래 연결 목록을 순회하는 새 노드 cur를 정의하고(원래 연결 목록이 변경되는 것을 방지하기 위해) x보다 큰 모든 것을 연결 목록에 넣고 x보다 작은 모든 것을 연결 목록에 넣은 다음 마지막으로 두 개를 연결합니다. 연결된 목록.

  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가 짧든 그 차이는 교차 전의 부분이기 때문에 긴 연결 리스트를 차이만큼만 이동하면 두 개의 연결 리스트 노드가 동시에 뒤로 이동합니다. 동일한 노드는 노드와 교차합니다.

  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. 순환 연결 리스트

연결리스트에 순환이 있는지 확인하는 방법:그래도 속도 지시계를 이용하면 마치 놀이터에서 두 사람이 달리는 것처럼 한 사람은 빠르게 달리고, 한 사람은 천천히 달리는 것처럼, 운동장은 링이기 때문에 반드시 빠른 사람이 느린 사람을 능가할 수 있다는 점에서 그들은 만났다. 하지만 타마키가 아니었다면 두 사람은 결코 만날 수 없었을 것이다. 마치 아무리 쫓아다녀도 잡을 수 없는 여신처럼 말이다.

그러나 또 다른 상황이 있습니다. 두 개의 노드가 있는 링이고 정의된 빠른 포인터가 한 번에 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 등 다양한 언어에 능숙하며, 오픈소스 분야에 많은 공헌을 해왔습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편