두 개의 연결된 목록의 교차점을 가져 오는 함수 작성


난이도 쉽게
자주 묻는 질문 수행자 아마존 드 쇼 팩트 셋 골드만 삭스 MakeMyTrip MAQ Microsoft 퀄컴 스냅 딜 비자, 조퍼
연결된 목록

문제 정책

"두 개의 연결된 목록의 교차점을 가져 오는 함수 작성"문제는 두 개의 연결된 목록이 제공된다는 것을 나타냅니다. 그러나 그들은 독립적 인 연결 목록이 아닙니다. 그들은 어느 시점에서 연결됩니다. 이제이 두 목록의 교차점을 찾아야합니다.

두 개의 연결된 목록의 교차점을 가져 오는 함수 작성

1 -> 2
      \
        5 -> 6
      /
3 -> 4
Point of intersection: 5

설명 : 입력에는 1, 2, 5, 6 및 3, 4, 5, 6의 두 개의 연결 목록이 표시됩니다. 둘 다 값이 5 인 노드에서 병합됩니다. 따라서 출력은 5입니다.

접근

문제는 설명하기 간단합니다. 두 가지가있다 연결 목록 그러나 그들은 어느 시점에서 결합되거나 상호 연결됩니다. 결합 지점 이전에는 두 연결 목록이 서로 다른 노드를 가지며 결합 노드 이후에 있습니다. 단일 목록으로 표시됩니다. 그렇다면 문제는 그러한 노드 (또는 포인트)를 어떻게 찾을 수 있는가입니다. 문제에 대한 가능한 답변 / 해결 방법이 많이있을 수 있습니다. 그러나 가장 간단한 방법은 연결 목록의 길이를 찾는 것입니다. 솔루션이 간단 할 때마다 시간 제한을 통과하는 것은 효율적이지 않습니다. 그러나 여기서는 그렇지 않습니다. 이 솔루션은 효율적이고 간단합니다.

설명

이 솔루션에서는 두 연결 목록의 길이를 찾을 것입니다. 그리고 더 긴 연결 목록의 머리 부분을 (레나 - 렌비) 노드. 여기 레나렌비 연결 목록 A와 B의 길이를 각각 나타냅니다. 그러나 우리는 왜 이것을 했습니까?

공통 연결 목록의 길이는 z이고 더 긴 목록의 길이는 x + z 더 짧은 연결 목록은 y + z. 그래서 지금까지 우리는 lenA – lenB 더 긴 연결 목록 위에. 그건 (x + z – (y + z)) = x – y. 이것은 우리가 현재 서있는 노드가 길이를 가질 때까지 더 긴 연결 목록 위로 이동했음을 의미합니다. y 더 짧은 연결 목록의 헤드의 결합 노드에서. 그런 다음 두 연결 목록에서 동시에 이동하고 현재 노드가 모두 같은지 확인합니다. 그렇다면 교차점을 찾은 것입니다. 그러나 연결 목록이 끝날 때까지 그러한 지점을 찾지 못하면. 그러면 교차점이 없음을 나타냅니다.

이것이 두 개의 연결된 목록의 교차점을 얻는 함수를 작성하는 방법입니다.

암호

두 연결 목록의 교차점을 찾는 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

struct ListNode{
  int data;
  ListNode *next;
};

ListNode* create(int data){
  ListNode* tmp = new ListNode();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

int length(ListNode *tmp){
    int cnt =  0;
    while(tmp != NULL){
        cnt++;
        tmp = tmp->next;
    }
    return cnt;
}

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    int lenA = length(headA);
    int lenB = length(headB);
    
    if(lenA > lenB){
        int cnt = lenA - lenB;
        while(cnt--)
            headA = headA->next;
    } else {
        int cnt = lenB - lenA;
        while(cnt--)
            headB = headB->next;
    }
    while(headA != NULL && headB != NULL){
        if(headA == headB)
            return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

int main(){
  ListNode *headA = create(1);
  headA->next = create(2);
  ListNode *headB = create(3);
  headB->next = create(4);
  headA->next->next = headB->next->next = create(5);
  headA->next->next->next = headB->next->next->next = create(6);

  cout<<"Intersection at node: ";
  cout<<getIntersectionNode(headA, headB)->data<<endl;
}
Intersection at node: 5

두 연결 목록의 교차점을 찾는 Java 코드

import java.util.*;
class ListNode{
  int data;
  ListNode next;
}

class Main{

    static ListNode create(int data){
        ListNode tmp = new ListNode();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static int length(ListNode tmp){
        int cnt =  0;
        while(tmp != null){
            cnt++;
            tmp = tmp.next;
        }
        return cnt;
    }

    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = length(headA);
        int lenB = length(headB);

        if(lenA > lenB){
            int cnt = lenA - lenB;
            while(cnt-- > 0)
                headA = headA.next;
        } else {
            int cnt = lenB - lenA;
            while(cnt-- > 0)
                headB = headB.next;
        }
        while(headA != null && headB != null){
            if(headA == headB)
                return headA;
            headA = headA.next;
            headB = headB.next;
        }
        return null;        
    }

    public static void main(String[] args){
    	ListNode headA = create(1);
    headA.next = create(2);
    ListNode headB = create(3);
    headB.next = create(4);
    headA.next.next = headB.next.next = create(5);
    headA.next.next.next = headB.next.next.next = create(6);

    System.out.print("Intersection at node: ");
    System.out.print(getIntersectionNode(headA, headB).data);
  }
}
Intersection at node: 5

복잡성 분석

시간 복잡성

의 위에), 연결 목록의 각 노드를 정확히 한 번 실행했기 때문입니다. 교차점이있는 경우 해당 노드에 도달하면이를 반환합니다. 그렇지 않으면 각 노드가 한 번만 순회됩니다. 이것은 시간 복잡성이 선형임을 증명합니다.

공간 복잡성

O (1), 우리가 저장 한 유일한 것은이 알고리즘이 일정한 공간만을 차지하게하는 연결 목록의 길이입니다.