Напишите функцию для получения точки пересечения двух связанных списков  


Сложный уровень Легко
Часто спрашивают в Акколит Амазонка Де Шоу Набор фактов Goldman Sachs MakeMyTrip MAQ Microsoft Компания Qualcomm Snapdeal Виза Zopper
Связанный список

Постановка задачи  

Задача «Напишите функцию для получения точки пересечения двух связанных списков» гласит, что вам даны два связанных списка. Но это не независимые связанные списки. В какой-то момент они связаны. Теперь вам нужно найти точку пересечения этих двух списков.

Пример  

Напишите функцию для получения точки пересечения двух связанных списков

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

Объяснение: На входе показаны два связанных списка: 1, 2, 5, 6 и 3, 4, 5, 6. Оба они объединены в узле, значение которого равно 5. Таким образом, на выходе будет 5.

Подход  

Проблема описывается просто. Есть два связанные списки но в какой-то момент они соединяются или взаимосвязаны. Перед точкой соединения оба связанных списка имеют разные узлы, а после узла соединения. Они представлены единым списком. Итак, проблема в том, как найти такой узел (или точку)? Возможных ответов / решений проблемы может быть много. Но самый простой способ - найти длину связанных списков. Когда решение простое, оно недостаточно эффективно, чтобы выдержать установленный срок. Но здесь дело обстоит не так. Это простое и эффективное решение.

объяснение

В этом решении мы собираемся найти длины двух связанных списков. И затем мы переместим вперед заголовок более длинного связанного списка на (ЛенаlenB) узлов. Здесь Лена и lenB обозначают длину связного списка A и B соответственно. Но зачем мы это сделали?

Смотрите также
Преобразование числа в решение Leetcode в шестнадцатеричном формате

Считайте, что длина общего связного списка равна z, длина более длинного списка равна х + г а список с более короткими связями у + г. Итак, до сих пор мы переехали lenA - lenB над более длинным связанным списком. Это (х + г - (у + г)) = х - у. Это означает, что мы переместились по более длинному связанному списку до тех пор, пока узел, на котором мы сейчас находимся, также не приобрел длину. 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

Анализ сложности  

Сложность времени

НА), поскольку мы прошли через каждый из узлов в связанных списках ровно один раз. Если существует точка пересечения, то, когда мы достигаем этого узла, мы возвращаем его. В противном случае каждый узел проходит только один раз. Это доказывает, что временная сложность линейна.

Смотрите также
Цикл связанного списка

Космическая сложность

О (1), единственное, что мы сохранили, - это длина связанных списков, поэтому этот алгоритм занимает только постоянное пространство.