Intersection de deux LinkedLists-tutoriel Java-php.cn

Intersection de deux LinkedLists

PHPz

Libérer： 2024-07-21 08:54:58

original

607 人浏览过

Intersection of two 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, les deux listes partiront donc de la même longueur.
revenir 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;
    }
}

Copier après la connexion

以上是Intersection de deux LinkedLists的详细内容。更多信息请关注PHP中文网其他相关文章！