Пересечение двух односвязных списков

Задача:

Припустим существует два односвязных списка, которые пересекаются в некоторой точке и стают односвязным списком. Известно начало обох списков, но неизвестна точка пересечения. Также, не известны длины обеих списков и длины обох списков могут быть разными. Первый список может иметь n элементов, перед тем как он достигнет точки пересечения, а второй - m элементов, где m и n могут быть m = n, m < n, m > n. Реализовать алгоритм нахождения точки пересечения.

Представление односвязного списка

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }

Решение:

Есть много способов реализации даной проблемы и мы рассмотрим только два.

1) Брутальный способ.

В этом способе мы сравниваем значения списков поэлементно, что дает нам сложность O(mn).

Вот пример на Java:

//Brute-Force solution
public static ListNode getIntersectionNodeBF(ListNode headA, ListNode headB) {
         if (headA == null || headB == null) {
    		 return null;
    	 }
    	 ListNode tmp = null;
    	 while (headA != null) {
    		 tmp = headB;
    		 while (tmp != null) {
	        	 if (headA.val == tmp.val) {
	        		 return headA; 
	        	 }
	        	 tmp = tmp.next;
    		 }
        	 headA = headA.next;
         }
         
         return null;
}

2) Главная идея второго способа состоит в том, что если данные два списка имеют точку пересечения, тогда она будет в конце этих списков, тоесть конецы списков будут одинаковые. Но у так как наши списки могут быть не одинаковой длинны мы должны уровнять их прежде чем мы начнем их сравнивать.

Алгоритм:

  1. Найти длины (length1 and length2) данных списков.
  2. Найти разницу diff между длинами.
  3. Сделать diff шагов в большем списке
  4. Пройти оба списка паралельно, пока не будет найден элемент пересечения.

Пример на Java:


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
    	int length1 = 0, length2 = 0, diff = 0;
    	ListNode list1 = headA, list2 = headB;
    	while (list1 != null) {
    		length1++;
    		list1 = list1.next;
    	}
    	while (list2 != null) {
    		length2++;
    		list2 = list2.next;
    	}
		list1 = headA;
		list2 = headB;
    	diff = length1 - length2;
    	if (length2 > length1) {
    		list1 = headB;
    		list2 = headA;
    		diff = length2 - length1;
    	}
    	for (int i = 0; i < diff; i++) {
    		list1 = list1.next;
    	}
    	while (list1 != null && list2 != null) {
    		if (list1.val == list2.val) {
    			return list1;
    		}
    		list1 = list1.next;
    		list2 = list2.next;
    	}
    	return null;
    }
}
LikeMe: