Intersection de deux LinkedLists

Problème

Approche par force brute :

Complexité temporelle : O(N+M) où N et M sont la longueur de deux LinkedLists données.

Intuition

Trouvez la longueur des deux nœuds et obtenez la différence de longueur
Avancez dans la liste la plus longue par différence de longueur des deux listes, de ce fait les deux listes commenceront à partir de la même longueur.
revient lorsque les mêmes nœuds sont rencontrés.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = findLength(headA);
        int lenB = findLength(headB);
        ListNode A = headA;
        ListNode B = headB;

        int diff = Math.abs(lenA-lenB);
        if(lenA > lenB){
            A = travelAhead(A,diff);
        }
        else B = travelAhead(B,diff);

        return findIntegersection(A,B);
    }
    public ListNode findIntegersection(ListNode a, ListNode b){
        while(a!=null && b!=null){
            if(a.equals(b)) return a;
            a= a.next;
            b= b.next;
        }
        return null;
    }
    public ListNode travelAhead(ListNode head, int diff){
        while(diff-->0){
            head = head.next;
        }
        return head;
    }
    public int findLength(ListNode head){
        int count = 0;
        while(head!=null){
            head = head.next;
            count++;
        }
        return count;
    }
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!